I know you didn't want code, but it may be worth looking at some if you're stumped. Here's a Mario clone that someone built a while ago;
http://www.xtremevbtalk.com/show...threadid=27443
I haven't looked at the code, but I'm going to assume he used a tile based map of sorts. The reason I say this is that drawing a single large image on to the screen is slower then tons of smaller tiles (hard to believe, but it's true). If you're looking for examples there are some tile based map editors floating around the forums.. a search should pull them up. There should also be some tile based map tutorials that you can find with a quick search on google.
As for maps, text format should be okay unless you plan on doing some really large levels, in which case you may want to consider using binary to speed up the load time. However, binary is hard to debug, so if you run into a problem with your map loading/saving it may take a while to track down the exact problem. Since you're just learning I'd suggest sticking with text for now and then convert it to binary later on when you get all the kinks worked out.