Got it in one.
USS Starfish – this is either McHale’s Navy or Hellcats of the Navy
USS Abraham Lincoln - 20,000 Leagues Under the Sea
Cavorite Sphere - The First Men in the Moon
Fhlosten Paradise - The Fifth Element
The Busted Flush - Travis MacGee series by John D. McDonald
Gay Deceiver - The Number of the Beast
Almost missed it:
The Rolling Stone - Heinlein’s Space Family Stone, aka The Rolling Stones.
Here’s a bonus question: What was the original name of The Rolling Stone?
Gay Deceiver From the Heinlien novel “The cat who walked though walls”
Still to go:
Fin of God
Immer Essen
HIMS Executor
Arabella
USNC Iroquois
Gone Fission
Michael
Guinevere One
Tarantula
HMS Atropos
Splendor Hyaline
USS Reluctant
The Slippery Pig
INSS MacArthur
R-XM
Icarus
Columbiad
Boise
USS Montana
USS Bozeman
The Moldy Crow
Aluminum Mallard
The Betty
USS Orlando
Blue Midget
The Kite
SS Lady Anne
USS Sulaco
Valley Forge
USS Grissom
Asgard
USS Kiwi
CosmoStrator
HMS Indomitable
Bosda’s picks:
Hispaniola
Seaview
Thunder Child
I can’t believe somebody got USS Starfish: yes, Reepicheep, it’s from Hellcats of the Navy.
USS Bozeman as commanded by Dr. Frasier Crane in STNG
Thunder Child - War of the Worlds (specifically the Jeff Wayne version)
Seaview - Voyage To The Bottom Of The Sea
INSS MacArthur - The Mote In God’s Eye
HIMS Executor - Star Wars (Vader’s Super Star estroyer)
Michael - Starship. Can’t remember the name of it, but the story is the one where Earth is invaded by aliens with a herd instinct.
HMS Atropos - Seagoing. From the Hornblower series.
Nostromo - Starship, Aliens, I think.
USS Stargazer - Starship, Jean-Luc Picard’s command prior to the Enterprise.
Pequod - Seagoing; it’s the ship from Moby Dick, right?
Kobayashi Maru - Fictional Starship. I don’t recall whether there was an actual Kobayashi Maru, but either way it’s a ship used in the Star Trek Universe to measure Academy student’s handling of a lose-lose situation.
IAV Dortmunder - Ow. Because I know I know this… I just can’t remember. 
Columbiad - My head says “From the Earth to the Moon”, the Jules Verne one. If that’s right, starship.
USS Bozeman - Starship, another one from Star Trek, but I can’t remember anything about it.
The Moldy Crow - Annoingly familiar but I can’t remember.
Aluminum Mallard - From the name, i’m guessing Star Wars parody, so i’ll guess starship.
Blue Midget - Starship, Red Dwarf.
Moya - Starship, Farscape.
The Kite - Starship, Discworld.
Asgard - Starship, Stargate SG-1
Heart of Gold - Starship, Hitchhiker’s Guide
HMS Indominitable - Familiar, but I may be thinking of an actual ship rather than the fictional one.
Looking at other’s answers now… I can’t believe I didn’t get the Executor. :smack:
Michael is from Footfall
Atropos may be from The Mote In God’s Eye
USS Bozeman is from Star Trek.
I’d like to offer up for consideration:
Vrolijkheid
Sea Tiger
The SS Lady Anne is from an episode of Twilight Zone.
USS Reluctant is from Mr. Roberts.
Fhloston Paradise is a luxury starship from The Fifth Element. It’s also the name of a planet.
Oh yeah, the USS Sulaco is the ship from Aliens
The Weatherlight
Aluminum Mallard - starship. Built by Roger Wilco out of parts in a garbage scow in Space Quest 3.
Just to add a few:
Lying Bastard
Rodger Young
Spindrift
MCS Starcross
Rodger Young is from Heinlein’s Starship Troopers
Spindrift is going to drive me nuts. I know that one…
Land of the Giants
The Gone Fission is from The Simpsons.
Here’s my additions:
The Proud Anselmo
SS Ssssss
The Big-Ass Spanish Boat (okay, this last one might be cheating)