I like AoO's, and have always used them in my games. I think they are a great way by which the rules restrict certain actions in combat, for example moving right through a horde of enemies or firing a bow when someone is hacking at you with an axe.
That being said, I think they sort of
rely on that you use a battle map of sorts for your combats (thats not been a problem for me, as I always use a grid-map and miniatures for my d20 games). I know a lot of people do use AoO's without a map, but then I think it will be a little trickier to advocate when they do and do not take place.
probably remove them from the game, but I think it would take a bit of work as there are quite a lot of feats, class features and actions you can take in combat that are based on them.
To understand how they work, you really need to understand how a character threatens the space around him. Usually, a character threatens everything 1 square (5') away, but this can be more if he has Reach (armed with a long weapon, or if he's a big monster). These squares are called his 'threatened squares'. An AoO is provoked whenever an enemy does one of the two following things:
1) Moves out of
one of your threatened squares. Note that its when an enemy leaves, as opposed to enters, one of your threatened squares that you get an AoO against him. This is important as it allows enemies to move into close combat with you, but not move away, or around and past you as they wish (well they can, but you'll get to whack them an extra time for free).
Oh, and one more important thing; you do not
provoke an AoO if you just take a 5'-step. This is a special exception that makes it possible to slowly work your way around in combat and get into flanking positions and such.
2) Performs certain distracting actions while in one of your threatened squares. Such actions include firing a bow, casting a spell etc. The table 'Actions in Combat' (AE, page 155) notes which actions provoke AoO's.
Whenever an AoO is provoked (because of 1 or 2 above), you just get an extra attack against the enemy that provoked it. This attack is taken immediately, even if it isn't your turn, and can sometimes even disrupt what your enemy was doing (for example, if a sorcerer is trying to cast a spell, and you hit him hard enough, he might loose the spell). However, you may only make one AoO each round (unless, as Raven pointed out, you have the feat Combat Reflexes).
I hope this long post was in some way helpful...