To sum up:
1. Build your ports up as high as you can.
2. Wait until you get the "World is Round" message, about turn 160 or 170 (in the unmodded game I think it arrives about the year 1400).
3. At at least one of your ports, build the new upgrade that is available, Naval Drydock.
4. Once that is built, you can build Carracks. ONLY Carracks can make it to the New World; if the stack of ships includes any other kind of boat, they can't go.
5. Load on stacks of armies (cavalry is pretty devastating, as usual, against them).
6. Sail west (very, very slowly--it takes about 8 turns to cross the Atlantic as I recall, depending on where you land).
7. PROFIT!