When both of the switches are at the bottom, then both should be N-channel. The point of a P-channel is that you can put it at top of the load, because you turn them on by pulling the gate negative. The draw-back of P-channels is that you have to get the gate all the way up to the drain voltage to turn them off -- not possible with 5V logic controlling a 12V load. The work-around for that is to use a pull-up resistor (1/2W, 100 ohm, say) to pull the gate high, and instead use a cheaper signal-level N-channel to pull the gate low when turning it on. The problem with that is that you are trading off power loss in the pull-up for fast enough turn-on time in the P-channel.
Now, why do I keep talking about turn-on time? It's because the MOSFET gate works like a capacitor. When it is fully charged, it lets current flow through gate and source. When it is depleted, it stops the current flow. When it is in an intermediate state, some current flows, but there's also a significant resistive loss. MOSFETs can have very low on resistance, and very high off resistance, so the loss in "on" or "off" states is very small, and little to no heat sinking is needed. However, in the "in-between" state, the resistive heating is significant, and if you stay in that state for any significant fraction of the time, they will heat up past their tolerance level, and burn out. Hence, why single on/off switches are safer, and PWM is safer with lower switching frequency. Also, why you want enough current into the gate of the device to build up (or deplete) that charge quickly.
What do the pros do? They use special MOSFET driver circuits that can deliver very large current "spikes" for short periods of time; enough to quickly push the device on/off, but then just deliver enough to compensate for the internal losses, which are very small. Additionally, these drivers often are able to "totem pole" the output voltage above that of the input voltage, so you can use a N-channel device (typically cheaper, and lower Rdson, and thus better and cooler) even as a high-end switch. There will be a dedicated "boost" capacitor attached to the driver, where it will build up charge that it can then dump into the gate of the switch it's driving. I haven't found any of these in a DIP package, though -- all the cool kids do surface mount these days. I'm going to have to get into toaster oven re-flow soldering soon :-(