Once you've beaten the game once you can save anywhere.
If you haven't beaten the game, either finish a mini-dungeon (the small tower), a world dungeon (the castle for each world), or unlock a locked area (by using your star coins). All of these scenarios would let you save after.
Be careful on the use of star coins, though, as they are limited (the ones you can unlock). Also, getting star coins can get a bit difficult as you progress, so use it sparingly.
Did you make sure there is an existing SAVE file ifor New Super Mario Bros in the NDSSAVE folder.
If no SAVE file exists (.dat file) in the NDSSAVE folder of the same name as the game, it will not save any progress.
Name of NDS Game File on the CF Card: New Super Mario Bros.nds
Name of SAVE File in NDSSAVE folder on the CF Card: New Super Mario Bros.dat