How do I pick the best potatoes at the supermarket?
There are two basic kinds of potatoes: starchy and waxy. 

The difference is actually in the amount of starch in them. Starchy potatoes, such as Russet or Idaho potatoes are best for baking, since the starch will allow it to be nice and fluffy after it's baked. They don't hold their shape particularly well when cooked. If you cut into a baked potato, it should be crumbly and dry. 

Waxy potatoes include most fingerling potatoes, and most red potatoes. They hold their shape better when cooked, so they are good for soups and stews and potato salads. 

Yellow-fleshed potatoes such as Yukon Gold or Yellow Finn are in between, and so can be used for either purpose. Purple potatoes also seem to have medium starch, and so can be used for both. 

According to one cookbook I have (Moosewood Restaurant New Classics), there are two ways to determine which is which. If you cut the potato in half, the blade will have a film or a foamy residue on the knife. These potatoes may also stick to the knife because of the starch. 

The rules for the brine is to make it of 11 parts water to 1 part salt. A high-starch potato will sink (it's denser) and a low-starch one will float. 

Here's a good overview. 

Now as to choosing ones that will bake well, it really depends on size. You want potatoes that will bake evenly, so try to choose ones of similar size. I bake my potatoes directly on the oven rack so that the hot air can move freely around them. Try to give them lots of room for that. Also, if you wrap them in aluminum foil, they'll steam and won't give you the nice crunchy skin. (And I'd avoid any potatoes with irregular shapes -- the smaller diameter ones may cook before the larger ones.)

Large potatoes take about an hour to bake at 350F. Lots of small ones may take a bit less time -- experiment with your oven and your potatoes. I'd start squeezing slightly after about 40-45 minutes. If they yield when squeezed, they're probably done.