What are the differences among Cave Story versions?

TL:DR

Cave Story 3D (for the 3DS) is a 3D remake of the 2004 original where all the characters and levels are in 3D perspective. There are also a few "easter eggs" for fans of the older games.

The Full Story

There have been numerous new versions and unofficial ports of Cave Story since the original was released in 2004, so assuming you don't want to know the specifics of the TI-83 plus calculator port, I'll just mention the differences of the five official versions.

Cave Story ("The Original", Platform: PC, circa 2004)

The original freeware version, with 100% original awesome.

Cave Story (Platform: WiiWare, circa 2010)

A new and updated version of Cave Story, with revamped graphics, music, and new playmodes.

Changes include:

• Updated "progressive" graphics (480p) and new music, with the option to use the "old school" versions of both
• Five new playmodes, including Boss Rush, and the ability to play as Curly Brace
• Larger range of difficulty settings
  
  

Cave Story (Platform: DSiWare, circa 2011)

A DS port of the 2004 original, with some of the new features from the WiiWare version thrown in.

Changes include:

• Uses second screen as a map and inventory viewer
• A modified version of the "Boss Rush" game mode included in the WiiWare version
• An unlockable music player
  
  

Cave Story+ (Platform: Steam, circa 2011)

The awesomeness returns to PCs, with many of the WiiWare features included, plus some other things.

Changes include:

• An HD graphical overhaul, with music introduced in the WiiWare version, and the option to use the "old school" versions as well
• All game modes introduced with WiiWare version
• All new game mode "Wind Fortress"
• Native USB controller support
  
  

Cave Story 3D (Platform: 3DS, circa 2011)

Cave Story goes 3D, but remains a 2D side scroller... Maybe a picture will help:

source: gamesradar

Changes include:

• All levels and characters remade in 3D, with a "Classic mode" that puts the old 2D character sprites in the 3D world
• A "Dynamic camera system" that automatically zooms in at certain points in a level
• A few extra areas that were never included in the main game
• An unlockable "Time Attack Mode"
• A soundtrack remade by Danny Baranowsky of Super Meat Boy and Canabalt fame
• Numerous easter eggs for old fans of the game and "cross-over content" with nods to Prinny in the western version, and content from Crazy Climber, Ikki, and Dragon Slayer added to the Japanese version
  

  
  

Sources:

• https://en.wikipedia.org/wiki/Cave_Story#Versions_and_ports
• http://tinycartridge.com/post/1180342112/tiny-q-a-nicalis-on-cave-storys-jump-to-dsiware
• http://tinycartridge.com/post/1981857328/more-cave-story-for-dsi-owners-europeans
• http://gonintendo.com/?p=58121
• http://www.shacknews.com/article/71248/cave-story-now-available-via-steam
• http://www.destructoid.com/cave-story-3d-features-2d-sprites-nis-surprise-201157.phtml

Consider this an update/continuation of RedRiderX's excellent answer. It includes differences for Nintendo Switch (2017), 3DS eShop (2012), and free updates released for to Cave Story+ on Steam.

Cave Story (PC, 2004, Free)

The original one-man freeware release that started it all.

Missing features:

• Multiple save files (All other versions have 3 save files)
• Selectable difficulty levels
• Multiple graphical/soundtrack options

Other notes:

• Never officially released in English
  • English fan translation released by Aeon Genesis

Cave Story (WiiWare, 2010, $12)

First retail release of Cave Story with updated graphics, music, and game modes.

Included features:

• Two graphics options: Original and Remastered
• Two selectable soundtracks: Original and New
• Hidden Jukebox Sound Test
• Unlockable option to play as Curly Brace
• Boss Attack and Sanctuary Time Attack modes
• Three selectable difficulty levels

Cave Story (DSiWare, 2011, Unavailable [was $10])

A DS port of the 2004 original, with some of the new features from the WiiWare version thrown in.

Included features:

• Uses second screen as a map and inventory viewer
• A modified version of the "Boss Rush" game mode included in the WiiWare version
• Jukebox Sound Test

Missing features:

• Remastered graphics
• New soundtrack
• Boss Attack

Other notes:

• No longer available for sale after DSiWare shop shut down in March 2017

Cave Story+ (Steam/Humble Store, 2011, $15)

Cave Story returns to PC in what was previously considered the definitive version of Cave Story. (This honor now belongs to the Switch port)

Features include:

• Two graphics options: Original and Remastered
• Three selectable soundtracks: Original, New, and Remastered
  • Remastered soundtrack added in free update (originally from Cave Story 3D)
• Native USB controller support
• Machine Gun Challenge mode (added in update)
• Steam Achievements

Missing features:

• 16:9 Widescreen support

Other notes:

• Jukebox sound test must be unlocked by beating Blood Stained Sanctuary in under 3 minutes on Normal or Hard

Cave Story 3D (3DS, 2011, $40)

Full fledged remake of Cave Story with 3D graphics.

Included features:

• Fully recreated 3D modeled graphics.
• Remastered soundtrack by Danny Baranowsky of Super Meat Boy and Canabalt fame.
• 3 exclusive areas: Egg Corridor Detour, Inner Wall, and Falling Tower.
• An unlockable "Time Attack Mode".
• Numerous easter eggs for old fans of the game and "cross-over content"
  • Prinny Cap from Disgaea for Western version
  • Content from Crazy Climber, Ikki, and Dragon Slayer added to the Japanese version.
• 16:9 Widescreen display

Missing features:

• Option for original soundtrack
• Jukebox sound test mode

Other notes:

• Published by NIS America
• Never reprinted or released digitally

Cave Story (3DS eShop, 2012, $10)

Replacement/Direct port of the DSiWare port on the 3DS eShop.

Not to be confused with Cave Story 3D, which also released on 3DS.

Included features:

• Supports Stereoscopic 3D
• 16:9 Widescreen display
• Curly Story

Missing features:

• New and Remastered soundtracks
• Remastered graphics option

Fun fact: Amazon sells digital eShop codes for this version, but mistakenly uses screenshots from Cave Story 3D.

Cave Story+ (Nintendo Switch, 2017, $30)

Originally a near-direct port of 2011's PC release of Cave Story+. However, free updates have introduced additional features such as local co-op, making this the definitive version.

Features include:

• Two graphics options: Original and Remastered
• Four selectable soundtracks: Origanya*, Cave Story+, Remastered, and Famitracks
• 16:9 widescreen display
• Machine Gun Challenge mode
• Local 2 player co-op
• Skippable cutscenes

_{*No, that's not a typo. The soundtrack is actually labeled in-game as Origanya.}

Sources

• Cave Story Wiki: Version differences