First, determine the criteria under which you are operating.
- A good initial step is to consider the relative values of the two vehicles, to work out which you primarily wish to protect from the other. You will want to think about protecting:
- the interior trim, paintwork and upholstery of the car, both from scratching and tearing and from chain grease and general grime
- the paintwork of the bike from scratching
- the frame tubes from denting or being pushed out of track
- the wheels from lateral forces. Spoked bike wheels are very strong in the plane in which they are used, but can easily be put out of true if forced in a different direction. (If you are using disc wheels, you can afford a proper pair of wheel covers. And probably a bigger car.)
- vulnerable projecting parts like gear mechanisms and plastic mudguards
- handlebar tape and saddle covers from tearing
- tyre sidewalls from chafing
- How much space have you got? Clearly, as nocte's writeup demonstrates, there is a lot of difference between trying to jam a fully assembled tandem into a VW Polo or just dropping your stripped down road bike into the back of a pickup, although some of the same things matter. In addition, how accessible is the space?
- How much scope do you have for disassembling the bike? What tools do you need? Do you have the time and the expertise to use them?
Estate cars are obviously best - if you have room to put the back seat down, most will hold several fully assembled bikes laying flat; a Volvo 240 will hold a fully assembled long wheelbase touring tandem - and even quite small hatchbacks are easy to get several racing bikes in, upright and transversally with the wheels removed. For saloon cars, unless you have an extremely spacious boot, the only real option is to put the bike in across the back seat, wheels out, unless you value the bike little enough to have it sticking out of the back with the boot half-open. Two-door saloons are the most awkward, but with a bit of fiddling it is nonetheless possible to get two 23" frame road bikes with wheels removed onto the back seat of a two-door Mini. Obviously, there are easier external solutions - roofracks, boot racks and trailers, but they cause drag and noise and lie outside the scope of this writeup.
The first thing you may want to do before thowing your muddy mountain bike in on your mum's new cream suede upholstery is to give the bike a bit of a wipe down. Remember to take any half-full bottles out of bottle cages, as well.
What I said for wheels about all their strength being in one plane really goes for frames as well, so you want to make sure that the bike is not jammed in in such a fashion that the frame is subjected to loading from one side or might have heavy weights fall against it; the best bet is to stand it vertically, if the roof height allows, or put it on top of other luggage if it has to lie horizontally.
If the bike will go in with the wheels in place, or with only the front wheel removed, it is almost certainly better to do so. Not only does it involve less work, but it means that the removed wheels will not have a chance to bounce up and down against each other and/or the frame, while the hubs will prevent the fork ends being squashed together, the chain will be kept under tension (put the gears into the largest chainring and largest sprocket to minimise the amount the chain can flap about and knock paint off the stays) and the rear mech will be less exposed to bashing about. If you do have to travel frequently with wheels removed, you may be able to get hold of the plastic fork end spacers used for shipping new frames from a friendly local bike shop, or alternatively use hubs removed from an old pair wheels. Otherwise, if the chain is going to be loose, it might be worth securing it to some other part of the bike to minimise its movement - old fashioned toestraps are ideal for this, if you can get them - or wrapping a rag around it to minimise the amount of soiling and damage.
If you do remove wheels, it is best to store them vertically if you can, trying to minimise the amount of contact they have with each other or the frame. Be particularly careful with the freewheel; if all the bits are going to end up in a single heap, put it facing outwards so it neither tangles with the spokes on the other wheel nor gouges bits out of the frame. If you often carry wheels with very light tyres, it will be worth getting hold of a pair of wheel covers or tyre covers to prevent cuts in the sidewalls (and thus blowouts later on...). Also be careful what you are doing with the chainrings which will now be in a position to get caught up in or smear lubricant all over the upholstery.
If the bike has mudguards and/or luggage carriers fitted, the amount of space you will save by taking the wheels - especially the back wheel - out is rather reduced, and guards in particular will be far more vulnerable to being bent out of shape.
Taking off the pedals (you will usually need a 15mm open-ended spanner or a 6mm Allen key; remember that the left-hand pedal has a left-hand thread) reduces the effective volume that the bike occupies quite significantly, as well as removing a potentially damaging projection; this is particularly useful if you are carrying several bikes. If you leave the front wheel in, you may also be able to save some space by slackening off the handlebar stem expander bolt or clamp and turning the bars sideways.
If you can, find something to wrap the bike in; an old blanket, as used by house movers, is great; a normal single blanket will probably be enough to wrap a frame and a pair of wheels. Bubble wrap is also good; slightly less satisfactory are sheets of corrugated cardboard which don't wrap around the uneven shapes so well. This is particularly useful if you are carrying more than one bike, as otherwise you are going to get scratched paintwork somewhere, but also if you need to protect a frame from freetting against its removed wheels (and nice spiky cassette, etc.). Very lightweight tyres may well also need protecting with wheel covers or more bits of blanket, etc.