Recently I was told to add auto_increment primary key to all our tables because our database is going to be replicated (master-master solution). All our tables had some kind of primary key, but not all of them were autoincremented.
I looked through mysql documentation about replication and I didn't find any indication that this (auto_increment primary key) is required. So, did I miss something? Is it better to have autoincremented primary keys when database is going to be replicated?
Autoincrement primary keys are absolutely not required, but they're one of the more straightforward and simple ways of dealing with the funky entertainment you're about to have when dealing with integer primary keys and multi-master replication. You'll need to ensure that newly inserted rows on each master are able to be uniquely identified. You don't want server A to insert row 1 at the same time as server B inserts row 1, as when they transmit their logs to each other, they'll both complain about the duplicate key when they try to insert each other's row.
You'll want to read up on the auto_increment_increment and auto_increment_offset configuration settings, which will make autoincrement work sanely with multi-master.
Also, tables that use natural primary keys are sometimes (but not always) perfectly safe for multi-master replication. It depends entirely on the frequency and nature of inserts.
This being said, multi-master is a last resort and a bad idea unless you have a highly experienced MySQL DBA on staff. I say this from experience, as my employer has a three server multi-master replication loop in production.