Selecting a MOSFET for driving load from logic

You've got a luxury problem: there are thousands of FETs suitable for your job.

1) the logic level. You have 5 V, and probably less than 200 mV or so when off. What you need is \$V_{GS(th)}\$, that's the gate's threshold voltage, at which the FET starts conducting. It's given for a specific current, which you want to keep an eye on too, because it may be different for different FETs. Useful for you could be maximum 3 V @ 250 µA, like for the FDC855N. At 200 mV (or lower) you'll have a leakage current much lower than that.

2) Maximum \$I_D\$ continuous. 6.1 A. OK.

3) the \$I_D / V_{DS}\$ graph:

This one's again for the FDC855N. It shows the current the FET will sink at a given gate voltage. You can see that it's 8 A for a 3.5 V gate voltage, so that's OK for your application.

4) \$R_{DS(ON)}\$. The on-resistance determines the power dissipation. For the FDC855N it's maximum 36 mΩ at 4.5 V gate voltage, at 5 V it will be a little less. At 500 mA that will cause a 9 mW dissipation. That's more than good enough. You can find FETs with better figures, but there's really no need to pay the extra price for them.

5) \$V_{DS}\$. The maximum drain-source voltage. 30 V for the FDC855N, so for your 12 V application OK.

6) package. You may want a PTH package or SMT. The FDC885N comes in a very small SuperSOT-6 package, which is OK, given the low power dissipation.

So the FDC855N will do nicely. If you want you can have a look at Digikey's offering. They have excellent selection tools, and now you know the parameters to look out for.

You need a MOSFET that will turn fully on with your 5V input, the spec to look for is Vth (threshold voltage)
Note that this figure is only the start of turn on, so the drain-source current will be very low still (often you see Vds = 1uA or similar as a noted condition)

So if your Vth is e.g. 2V, you probably want around 4V to turn it on well - the datasheet will have a Vg vs Id/Vds graph to show you how much the MOSFET will turn on with different gate voltages.
Rds is the drain source resistance, which can tell you how much power the MOSFET will dissipate (e.g. Id^2 * Rds)

Also you need it to be rated for the maximum drain source voltage and drain-source current (Vds and Id) which is in your case 500mA and 12V. So something like Vds >= 20V and Id >= 1A will be fine.