I know the terms MIDP1.0 / 2.0 and CLDC, but have no real clue what that means to me.
MIDP 1.0, MIDP 2.0, CLDC (and other terms) just define what classes are available to the java program. You can find the listing on
http://java.sun.com/j2me/index.jsp- How do I know for sure I can write a java app using j2me and have it run on my cell phone?
You check with the phone specs. You can also verify with
http://jbenchmark.com/- How do you get the apps to the phone? Cable, network, other?
Typically using data cable, IR port, Bluetooth or OTA (Over The Air, basically upload to webserver and download).
I don't want to get a java enabled phone, only to find out I have to pay to download games and content from my phone provider only.
Well, you have to pay for others games

- you're free to do what you want with your own stuff