Mobile GMaps (MGMaps) is free Java Midlet (J2ME) mapping application, which uses OSM maps among several other sources (like Yahoo, MSN Live etc). It supports many different phones, has Bluetooth and internal GPS support, also enables off-line usage of map data.
Use with Open Street Maps
Mobile GMaps doesn't seem to have any tools available to record or export routes or waypoints. As such it doesn't appear to be very useful for map creation.
MobileGMaps excels at map viewing however, and is suitable for viewing large amounts of data. It can download and cache maps from the Internet, but there are also several methods of pre-caching map data. Caching methods are listed on the developer's Map Tile Caching Tools page.
While this software lacks the polish of some other offerings, it seems to be a robust choice for those who need to view OSM data on their handsets.
There is also commercial licensing available for custom projects from Nutiteq.
Cease and desist from Google
As an interesting aside, back in 2007 mgmaps used to support viewing google maps, but they received a letter from the "Google Enforcement Team". Arguably this is less a case of google being evil, and more case of google being more vigilant than Microsoft and Yahoo in protecting the interests and licensing requirements of their downstream data providers. In any case... mobile app developers are better off with OpenStreetMap :-)