How would I go about developing a simple IM which will be used on mobile phones. By this I mean creating a database to hold all the information needed to log on, the API's needed, security and everything that makes the motor spin.

Are you already familiar with Java? You'll need the java mobile kit (not sure what its actually called) and a server running MySQL or some other database. The server will also need to run the server program which accepts incoming connections from clients and routing all the IM traffic. Then you'll need to also write the actual IM client for the phone. I've never done anything for phones specifically, so you're on your own there.

Design your IM protocol first and determine what information needs to be stored. Then design your database structure (tables, fields).