How to get a bike from one city to another in the U.S
I've never shipped a bike, but I moved from Canada to Europe with my Surly Cross-check in a box last year. When the box came off the plane it looked like it had been run over by a truck and left out in the rain, but the contents of the box were 100% undamaged.

Hold on to your pants, this is gonna be long!

Shipping a bike is cheap and easy, but make sure to do it right. 

As I'm sure you have found out airlines require you to have your bike in a box or a case. Cases are expensive. Most bikes are shipped to bike stores in a cardboard box in various stages of assembly from just a frame to a full bike with some parts removed for transport. When they unpack new bikes they have to get rid of the boxes so hopefully you can find a nice store that will give you one for free or sell you one really cheap, like 10 bucks or less.

If bike stores are no luck then furniture and appliance stores and bed stores like Sleep Country are great sources of large, strong, and free cardboard boxes and large strong plastic mattress bags, both of which you'll need. These stores are also usually overflowing with bubble wrap, styrofoam peanuts, little air filled plastic bags, and all sorts of other packing materials and are usually willing to give the stuff away if you want to root through the dumpster. Also recycling depots are always overloaded with cardboard, all free. Just think creatively and you should be able to find all the materials you will need for free in our mega-packaged and plasticized world.

So here's how (I think) you should pack your bike:

Materials List


Large strong cardboard box that will either fit your bike or can be easily cut and folded to make the right size box. Mattress boxes, fridge boxes, and large flat screen tv boxes are perfect. Just try to choose a box that is as long as your bike plus a couple of feet, and as tall as your bike plus a couple of feet, so you can have plenty of room to fold over the ends, top, and bottom. Just think of how you would size up a piece of wrapping paper before wrapping a present. I hope you are good at wrapping presents.
More flexible (but still corrugated) cardboard that you can roll like Xerox paper box type cardboard.
Lots of newspaper, bubble wrap, styro-wrap... whatever you can scrounge for padding and space filler. Plastic shopping bags make great padding and can usually be had by the thousands from friends who would love to get rid of the bags of bags they have in their hall closets or kitchen drawers.
Several rolls of 2" clear packing tape. Usually sold by the 6 pack pretty cheap or else sold per roll for the small price of an arm and leg at the UPS store, post offices, U-haul and other 'specialty' packing stores.
good box knife and/or good scissors


Procedure

Bike preparation:

You have three options:
a) leave the wheels on the frame and make a box big enough for the whole bike, or 
b) remove the wheels and package them in a separate box, or
c) a combo of the two, which is what I did (remove front wheel, leave rear wheel on and pack it all in one box). 

Check with the airline for fees per box and weight restrictions on the boxes to decide.


remove pedals (and crank arms if you wish to package them separately but this isn't necessary IMO)
release the tension on your cables but leave them attached, so basically just crack the nut so the cable is for sure slack and then re-tighten gently to just hold the cable there. You mention this is a fixie so likely no shifter cables but maybe a brake cable, maybe not.
loosen stem and turn handlebars 90 degrees to they are parallel to your top tube. If you have drop bars or aero bars you may want to remove them all together, they can be placed inside the triangle of your frame when you pack the bike, but if you have any cables it is easier to leave them on the stem.
push seat post down into tube all the way but leave the seat on the bike, it is a good spacer against side impacts.
air down your tires but leave them spongy enough that you could just ride them. This will allow them to expand and contract during the flight but keep them seated on the rim during packing and transport


Padding

I am going to assume you are using one box but if you decide to ship the wheels separately then just don't put them back on the frame.


remove wheels
using the more flexible cardboard cut a strip the width of your top tube and long enough to go around a couple of layers thick. Roll the cardboard around the tube firmly and tape in place, tabs are sufficient but you can wrap right around with the tape if you wish. Don't be stingy with the layers, put three layers if you want, make sure the cardboard goes right to the butt joints at either end.
repeat this process for the down tube, seat tube, stays and fork arms. Basically just cover all the long and delicate parts of your bike with a nice thick roll of cardboard. If you are putting your wheels back on the frame make sure you leave enough space so they can fit back on, depending on how thick your cardboard is maybe you'll only get one or two layers on the stays and forks.
do a similar wrap on your handlebars and cranks but use bubble wrap if you have some, or just a few sheets of newspaper. Hold in place with a tab of tape.
bubble or newspaper wrap other exposed sections of the bike if you wish such as brakes, stem, tube junctions
replace your wheels and tighten them on firmly. They should fit snugly between the cardboard padding.
if you managed to get a hold of a good solid plastic mattress bag (double or queen should do) then I would bag the bike and tape it shut. If for some unknown reason the box is left out in the rain or snow, or something in the luggage gets all over it you have an extra layer of protection.


After this your bike should be pretty well padded, time to put it in a box or build a box around it.

Boxing

Float like a butterfly and sting like a bee, stick and jab... oh right, cycling. This kind of depends on whether you have a bike or mattress box that is already close to the right size and whether you are leaving your wheels on or not. I will assume you are building a custom box and leaving the wheels on.

IF YOU ARE TAKING YOUR WHEELS OFF, PUT A SPACER of some kind between your forks and stays where the axle would be to keep them from getting squished together if the box is compressed for some reason. 

ALSO - MAKE SURE YOU EITHER REMOVE AND/OR PUT A BLOCK, SPACER, OR SOME KIND OF PADDING around your rear derailleur (if you have one, fixie riders can ignore this bit), otherwise you risk having it broken or damaged by careless airline tossers.

A block of wood like a piece of broomstick taped in place works fine, or perhaps you have (buy or scrounge from an old bike) a couple of solid axles that you can just pop into the dropouts, with one set of nuts inside the fork screwed out gently against the fork and the other on the outside screwed in gently against the fork, sandwiching the forks/stays in place.

Scenario 1 - you have a mattress box or bike box that is the right height and length and just need to drop the bike into it.


layer the bottom with a mass of firmly balled newspaper
lower the bike into the box
starting at the bottom pad around the wheels until the bike will free stand in the box. Firmly balled newspaper or bubble wrap is best.
once the bike is standing nicely you can begin to fill the rest of the space.


Styro peanuts, those air filled spacer bags, and bubble wrap are great for this. Loosely balled newspaper is excellent padding too. If your bike is in a clean(ish) plastic bag then extra clothing is good padding and space filler, and might cut down on the size of your checked luggage or carry on. Bulky items like jackets and pants for example. Or put your clothes in bags as well perhaps.


if you have removed the handlebars now is the time to place them in the triangular space and fill around them with packing.
bike parts that you have taken off such as pedals and cranks can be wrapped and places strategically in the empty spaces. Bike tools (to put it back together), tire pump, helmet, and other accessories can also be wrapped and used to fill the space.


When the box is full of packing to the top, close the top flaps and tape every single edge and seam closed. More on this later

Scenario 2 - you have a large box like a fridge box or mattress box that is way too big and you need to custom make a box.


measure how wide your bike is at its wides point, usually the BB or handlebars
cut the box along one corner so that it can unfold and lay flat on the floor. Choose the largest side and lay the bike on its side on top of the box leaving enough room so that the top parts of your bike (seat and handlebars or stem) are below the top edge of the box by the WIDTH of your bike PLUS 4 inches. You are going to fold the top of the box over eventually and this much space will allow you to fold the top over completely making the box wide enough for your bike with 2 inches of space on either side of its widest point. Mark a line across the box at the level of your tallest part. This is where you will fold the box to make the top.
make similar measurements and mark lines on the box where you will make folds for the bottom, and then for the top again, cut off any excess cardboard. Don't worry about the length yet, you just want to wrap around the bike first.


Creasing and folding these large strong boxes can be difficult to do in a straight line. One way is to pick the box up on edge and use the corner of one of your walls as a straight edge. Stand the box up flat against one wall with the line against the corner and fold the box around the corner. This should give you a good fold and not take too much effort. If you have a big table or long counter top you could use that too.


make all your folds so that you have a box with open ends and an open top.
once the box is folded it should be easy to mark, cut and fold the end flaps and then tape them shut so that you can lower the bike into your new box.


I recommend making all of your top flaps and end flaps the full width of the box. This makes each end a double layer of cardboard and also makes taping the edges together much easier because you can just butt the folds together and tape tightly. True, the sides and bottom are still a single layer but... meh.

So now you have made a box just the right size for your bike with the top flaps still open. Proceed as above under Scenario 1.

A Note on Taping

Here's how I tape closed a box that I want to be strong and secure for shipping.


close your flaps and use tabs (4-6 inch long strips of tape) to firmly hold them together. For a bike sized box I would have at least 6 tabs on each end.
once an end is made, tape each corner along its length with two strips of tape, first off setting the tape slightly to one side, and then to the other. Lay the tape strip lengthwise along the edge and then fold it over, off set to the other side and repeat. This gives each corner a double layer of tape.
once the top is closed and the flaps are secured as I just described I would now tape right around the box 3 or four times. To go from top, down the side, under the bottom, up the other side, and across the top again. Three or four strips evenly spaced. Do the same from end to end 2 times as well.
if any of the seams or corners still seem weak at this point, tape the heck out of them.


Labeling

Check with the airline again regarding any restrictions (or requirements) on labeling but I put my name on the box in big black sharpie as well a safe 'return' address. At least if the bike got lost it would get back to my folks place and I could have it shipped again. If you know your destination address then put it on there too, kind of like you would address an envelope.

Add labels like 'This End Up' with arrows or 'Do Not Lay Flat' to keep the box upright so they won't lay it flat and pile stuff on top of it.

'Do Not Squish'
'Do Not Bend'
'Fragile'

may also be useful.

Well, that's all I can think of. If your bike gets damaged after packing it this securely then I think you will have a pretty good insurance case against the airline.

Oh and on that note get insurance on the bike for the trip, possibly through the airline, and take pictures of the bike during various stages of packing to prove your efforts and show that it's really yours.

Paranoid enough?

Good luck and Bon Voyage!

ps. If you're traveling with the bike, remember to pack the tools needed to put your bike back together.