I downloaded GMod a couple days ago, and since then I've been playing it like crazy! I've downloaded gun mods and such, but now I want to play on an addon map from the workshop. They've never shown up the entire time I've had the game.....
Are you sure you downloaded a new map and not someone's saved game? New maps should automatically show up when you click "new game".
Try clicking the "saves" button on the menu and see if what you were looking for shows up. If it was not a save, then head over to your steam install directory>steamapps>common>garrysmod>garrysmod>maps and see if there is anything in there relating to what you were trying to download.