Well, to start off with, IVs have different security properties than keys. With keys (as you are well aware), you need to hide them from anyone in the middle; if someone did learn your keys, then he could read all your traffic.
IVs are not like this; instead, we don't mind if someone in the middle learns what the IV is; as long as he doesn't know the key, he still can't do anything with the encrypted traffic. Because of this, one common practice is to have the encryptor select the IV, and then include it along in the encrypted message (generally immediately before the ciphertext). This eliminates half your problem (how does the decryptor know which IV to use; he gets it out of the message); the attacker can see the IV as well, but (as above) we don't care about that.
So, the question comes down to "how does the encryptor select the IV"? Well, the answer to depend comes down somewhat as to the mode you're using; the requirements for IVs differ depending on whether you're using CBC or CTR mode.
For CBC mode, the statement you list is mostly accurate (although I would write it as "You SHOULD use unique IV's everytime you encrypt, and they MUST be unpredictable"; there are known attacks against predictable IVs; I don't know if they apply to your scenario, but it's generally safer if we don't have to worry about them at all). There are several ways do to this; a cryptographically secure PRNG (with good seeding) works. Another thing that I've seen is you take a counter (say 0 for the first message, 1 for the second, etc), encrypt that (in ECB mode) with the same key you'll be encrypting the message in, and use that ciphertext as the IV. This works because the ECB encryption of a counter is unpredictable to anyone who doesn't know the key. Of course, if both ends of a bidirectional channel use this method, they need to either use different keys or make sure that their counter values won't overlap (e.g. one end could use only even values and the other only odd ones).
For CTR mode, the statement is less accurate; it would be more properly "You MUST always use unique IV's every time you encrypt; predictability is not a concern". Because of this, it is common to use a counter as the IV; we get uniqueness (counters obviously never repeat within the lifetime of the key), and while it is predictable, we don't care about that here. Now, there is one note: the uniqueness requirement doesn't just apply to the IV's, it also applies to the values you present to the block cipher. Because of this, one common approach for CTR mode is to take the 16 byte AES plaintext block, and divide that up into (say) a 12 byte IV field and a 4 byte message index field; during the encryption of a single message, the IV field is always the IV value we are using to encrypt/decrypt the message, and the message index field increments for every block we encrypt; say, 0 for the first block, 1 for the second, etc.
Lastly, while you haven't specifically asked about this, I believe a heads-up is required; usually, when we encrypt a message, we generally need to use an integrity check as well (to make sure that the message received was the message sent); even if you don't particularly care about message integrity, there are several clever ways for an attacker to find things about about the encryption by modifying the cipher text, and seeing how the receiver reacts. The short answer is that you should include some integrity transform (be it HMAC, CMAC, or replace the entire encryption operation with a primitive that does both privacy and integrity, say, GCM or OCB). However, to fully discuss this requires more space than I should take up in the answer to a different question.
