Actually, Evilsteez and Muerteverde, this isn't true (not scientifically, anyway). I think for your regular cross-trainer it is, because they don't swim correctly, but in fact, butterfly is the most efficient of all the strokes, and breastroke is the least efficient. However, this is what has been proven physically in labs studying olympic caliber swimmers.
Myself, I could never swim butterfly for more than 8 laps without gassing, but the guys who specialized in that stroke, like my brother, they could just go for days and days without even trying. If you ever see a competitive flyer, watch him flow in practice, and see how many strokes he takes across the pool. My brother, at cruising speed, would get across in 7-8 every time.
Choosing which stroke to swim would probably be best decided on whichever you could maintain constantly without overexerting yourself. If you can swim the breastroke nonstop for 20 minutes without burning out, that's the one for you. If it's freestyle, great, crawl. Some guys love the backstroke; they relax better, and naturally lay their heads back, balancing in the water better than on their stomach, and usually turn from side to side better more smoothly and completely, thereby making their stroke more efficient.
Apart from that, it's just which muscles you want to work. Each stroke is more intensive on certain muscle groups, breastroke being the most unique, but mainly they all hit your shoulders and triceps the hardest.
Careful, though, everyone, because you can injure yourself swimming too. Shoulder and tricep tendinitis are common among swimmers, and the way non-swimmers swim flat in the water, I get really concerned with your shoulders thinking about you guys going after it.
Total Immersion is in my opinion the best source for learning to swim for beginners who have no one to formally train them.