For 3DS:
If you already own Shovel Knight vanilla, go to the page for Shovel Knight: Treasure Trove.
Even if it says it's $25 or whatever. Go there, and there will be a button at the bottom for the update. It's free.
Wow....that's really antiquated. Both my PC and PS4 updated to Treasure Trove without me needing to do anything. I'm not sure about Wii U though since I haven't turned mine on in a few weeks.