I would suggest starting with a smaller H-bridge project first. The control of MOSFETs seems simple, but there are some subtleties which can easily bite you if you are not careful. When designing a smaller H-bridge project, it's not too hard to protect a circuit in such fashion that even if something goes horribly wrong it won't do much damage (and may very well not do any, though whatever caused the problem will need to be fixed in any case). This is useful not only from the standpoint of reducing the amount of time spent replacing blown components, but also from the standpoint of being able to figure out what happened. If something goes wrong in a 12V 30A H-bridge controller, it's likely to cause enough destruction quickly enough that it will be hard to analyze the pile of cinders and determine what failed first.
Beyond that, the reason companies make H-bridge controllers is that other companies buy them, and the reason that other companies buy them is that a surprising number of discrete components are required to safely and optimally control a MOSFET. If one is trying to control a MOSFET whose Absolute Maximum Vgs is 15 volts, and an inductive transient causes Vgs to reach 30 volts even for a microsecond, the part may easily be destroyed (the voltage required to destroy the part would most likely be around 20 volts, but one shouldn't rely upon it being above 15.01). Keeping Vgs below 15 volts may not sound hard, but factors like parasitic gate-drain capacitance can lead to some unpleasant surprises.
FET Type: I'm not sure what the difference is between N and P channel
The internal construction of a mosfet is different and you need different voltage levels to switch it on. Higher than source for N channel and lower than source for P channel. As you will be switching 25V load from a 5V microcontroller, choose an N channel logic level mosfet.
Drain to Source Voltate (Vdss): I'm assuming this is the max voltage it can handle going through it, so I should be finding a MOSFET that will support 25 V+?
It's the maximum voltage whitch the mosfet can withstand without letting the current to run through it.
By the rule of thumb you should double the rating to get a reliably working system. So, look for a mosfet with Vds in the range of 50V-60V. It would be OK to use a 25V mosfet but you usually don't want to operate near maximum limited values.
Current - Continuous Drain (Id): Assuming this is the max amperage going through it, so looking for one with 12.5 A+
Again - double it.
Vgs(th) (Max): I think this has something to do with the activation voltage applied to the gate that will make it activate, so I need one with less than 5 V?
Yes, mosfet dissipates least power when it's either fully on or off. Look at the graphs in the datasheet that specify Rdson depending on Vg - you want Rdson as small as possible, so you want to drive the gate above the Vgth. But note, that there is a maximum value that can be safely applied to a gate - Vgsmax. You should be safe driving it with a microcontroller, just a point to note.
Power - Max: Assuming this is the max power it can handle. I've calculated the power the solenoid would need as P = V*I = 25 V * 12.5 A = 312.5 W, so I need a MOSFET that can handle more than 312.5 W?
No, power dissipated by a mosfet would be I*I*Rdson - that's why you want as little Rdson as possible.
I don't know what Rds On (Max), Gate Charge (Qg), or Input Capacitance (Ciss) mean. Are they important for my uses?
When a mosfet is on, it's not an ideal conductor with no resistance. Rdson is the resistance of the mosfet and is dependent on different factors, datasheets usually give graphs how Rdson changes with different parameters.
You don't have to deal with gate charge and input capacitance in you application as fast (submilisecond) switching is not required. A mosfet gate presents itself as a capacitor to a driving circuitry and as it takes time for a capacitor to charge, it takes time for a mosfet to turn on that's why in high speed applications special mosfet driver ics are used that force high currents into gate to charge this capacitance as quickly as possible.
You can find cheaper mosfets with lower Rdson, just use the parametric search on digikey. Pay attention to the graph that displays Rdson against Vgth - sometimes manufacturers claim 4V Vgth and 4mOhm Rdsn, but when you look at the graph you see, that at 4V it's 20mOhm and you need to get to 9V to get the advertised 4mOhm Rdson.
Best Answer
The charge-discharge voltage of the gate, is between the gate-source of the MOSFET.
You need to drive the gate of the P-MOSFET to the source voltage that, in your case is 18V to turn it off.
As you say, you are getting near 5V at the gate, so the P-MOSFETS are always conducting, and the N-MOSFETS are switching.
You are basically shorting the bridge at the PWM frequency and duty-cycle. To confirm, measure the current consumption, even with a low output current it should be high.
Also
This is just a sketch
With this circuit the P-MOSFET gate-source will be 0V (thought pull-up resistor) and it will be non-conducting. When the NPN transistor is conducting it will pull the P-MOSFET gate-source to a low voltage (you can change the pull-down resistor to adjust this voltage).