In the past I've seen carseats on the baggage belt in clear trashbag size bags with "Southwest" stamped on them, but it's been over a year since I've flown so I can't confirm they still have those, or that they are free.

If you travel frequently, we practly ran the wheels off of this: http://www.strollerdepot.com/moreinfo.php?SKU=0012
There's even a commercial here: http://www.sitnstroll.com/
Can probably find a used one on eBay, that's what I did with ours when the kids outgrew it.