Regardless of what the airline says, look at this from the perspective of the car seat manufacturer. Most advise that car seats should not be checked as luggage because they can sustain impacts during baggage handling that can cause weaknesses and stresses that will compromise the seat's ability to protect in a car crash.

Best advise is to take both the car seat and stroller to the gate. Gate check the stroller and use the car seat on the plane. If traveling with a lap infant, gate check the car seat.

Personally, I would recommend getting the car seat travel bag (graco has one specifically for their seats, but here is a link to many: http://www.amazon.com/s/ref=nb_sb_no...o+car+seat+bag) and a stroller travel bag (Kelty makes a great padded one, but here is a link to many: http://www.amazon.com/s/ref=nb_sb_no...ler+travel+bag) to put them in at the gate. We used them with our children and the bags are great to prevent germs, dirt, rain, snow, etc from getting into the padding of the seat and also helps prevent plastic pieces, wheels, etc from getting snapped and damaged on the stroller.

As for the tag when you roll up to the gate and put them in the bags before getting on the jetway, then drop at the door with all other gate check lines.