Depends on the phone. On a Symbian, you just downloaded a SIS file; later versions required code signing. Afaik, WinCE and Palm phones were similar. I had some java capable feature phones that were similar, put together a jad file and hope that write once, run everywhere works (I remember my first phone had some features that used a J2ME standard interface exactly backwards; turn on backlight would turn it off, and vice versa). I didn't even select those two phones for their openness, I just had them and tried to write/run code and it was available.

Certainly, the carriers had stores, but it's not like they had software I wanted to run.