Check out this little gem of information courtesy of PBS

http://www.pbs.org/lostliners/ocean.html

QUICK SYNOPSIS:

In 1819, the "Savannah", an American sailing ship with auxiliary steam
engines and two paddle wheels that could be folded away on deck, made
the first steam-assisted crossing of the Atlantic.

In 1831, a Canadian ship-the paddle steamer "Royal William" finally
crossed the Atlantic primarily under steam.

In 1838, the "Sirius", a new coastal steamer temporarily commandeered
for a transocean voyage, became the first ship to cross the
Atlantic under continuous steam power.

Launched in 1837, the "Great Western" made her maiden voyage from
Bristol to New York in April 1838.

In 1858 The "Great Eastern" (largest paddler in the world) was
launched and made her maiden voyage in 1859. The rest, my friends, is
Paddlewheeler history.

PJ
Sources PBS and BBC