As many great comments that have been made on this thread, my OP was really seeking knowledge about ocean travel in general, and the specific technologies and knowledge that allow it.
What prerequisite knowledge is required to invent the compass and apply it to navigation? Was that knowledge available to the Phoenicians?
Is the carvel build necessary for sustained trans-atlantic travel? What forces lead to innovations in ship building?
How did cultures IOTL come by their knowledge of oceanic currents and trade winds? How was the Volta do Mar discovered, and is it reasonable to believe that it could have been discovered much sooner?
In general, is it possible that a seafaring culture such as the Phoenicians could and would be able to initiate trans-Atlantic travel and trade more than 1500 years before the Portuguese and Spanish?
Weren't the Phoenician ships already somehwat ocean worthy? And if they weren't, and they saw profit in sailing into the sea for some reason, then they certainly have the ability to create oceanworthy vessels.
Anyway, on the compass: Going off of Wikipedia here: "The magnetic compass was first invented as a device for divination as early as the Chinese Han Dynasty (since about 206 BC)."
Now, this was not used for navigation in China until about the 9th and 11th centuries. However, again according to Wikipedia:
"The earliest Chinese literature reference to magnetism lies in the 4th century BC writings of Wang Xu : 'The lodestone attracts iron.' The book also notes that the people of the state of Zheng always knew their position by means of a "south-pointer"; some authors suggest that this refers to early use of the compass.
The first mention of a spoon, speculated to be a lodestone, observed pointing in a cardinal direction is a Chinese work composed between 70 and 80 AD (Lunheng), which records that "But when the south pointing spoon is thrown upon the ground, it comes to rest pointing at the south."
This is one of those few Wikipedia articles that are actually extremely detailed and well researched:
http://en.wikipedia.org/wiki/Compass#Navigation_prior_to_the_compass
As for trade winds, I presume they would just be discovered and figured out by simple trial and error.