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 &micro;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&Omega; 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.