If you want to get a wrap for a newborn a wrap with some stretch in it is best. Once they're older you don't really want any stretch because stretch wraps have a tendency to stretch out (only talking wraps here). Wraps are hugely versatile but the downside is the learning curve and that they are a lot of fabric. In the climate I live in a wrap is almost useless in the summer (Temps are in 90s-100s) - I would get way too hot. Another option is a ring sling. They too have a learning curve but aren't as much fabric. Wanderlost mentioned a mei tai. Those are nice and you can use them with newborns but I don't think they replicate the womb experience as much as a sling. I used a mei tai quite a bit around the house w/ Logan when he was around 6 months to a year because he liked it for some reason and it was the only way to get him to sleep.
My all time fav for a new mom inexperienced with babywearing is a pouch style sling. There are a few main brands - hotslings, peanut shell, kangaroo korner, new native and lucky baby. Many WAHMs make them too. Like Wanderlost said I do sell Hotslings - I love them that much. Pouches have the smallest learning curve and as long as you get the right kind (STAY AWAY from the ones sold in target and babies r us - they're terrible - except some targets are now selling hotslings) they replicate the womb experience. Most pouches except the kangaroo korner ones aren't adjustable so you need to get the right size. I don't like the way the new native pouch fits on a mom so I never recommend them. With any sling you want a snug fit with baby high on your body.
The great thing with any sling is that they can be used from newborn to toddler and they're not too expensive. What other baby product can you buy for $40 that will last you a couple of years?