You can follow Facebook Connect's example. A few points there..
1. Logins must be done on HTTPS. On the SSL level, the client must authenticate the server's certificate - i.e. the client must check whether the server's certificate is properly signed by a trusted CA, and whether the server peer name matches the name that's being connected to, e.g. api.example.com. This means nobody will be able to intercept the encrypted passwords via man-in-the-middle attacks (e.g. by hijacking a DNS and redirecting traffic to his fake api.example.com server).
With proper server certificate authenticate in place, only the person/company/server with api.example.com's private key will be able to decrypt the HTTPS traffic going into api.example.com. So as long as nobody working for example.com posts the private key on Slashdot or HN, nobody outside of example.com will be able to intercept the login passwords - assuming they don't have other security holes like SQL injection problems.
2. HMAC or HMAC-like scheme based on shared secrets and sequence numbers. If you intend to let clients use your API via HTTP instead of HTTPS after the login step, e.g. for performance reasons - frequent HTTPS handshake can slow your app down a lot when you take network latency into account - you'd need to have a way to authenticate your clients on the clear without using passwords or just simple cookies.
What Facebook's HMAC-like scheme does is that they'll send a shared secret to you on HTTPS, in addition to just the open session key, when you login. Any FB Connect requests would have a session key, a sequence number, and an md5 hash of the whole requests appended to the session secret. Because nobody else knows the the session secret, the only person who can generate the correct md5 hash for that request is you. So even if an attacker can intercept e.g. a Facebook status update from HTTP, he wouldn't be able to change it or post something else to your wall later. The sequence number is there to prevent replay attacks so the attacker wouldn't be able to post the same message again.
RE: point 2, The Facebook Graph API (which will at some point deprecate the Old REST API) does not operate in this fashion. You receive an OAuth access token and pass it back to FB over HTTPS. Unlike the Old REST API, no MD5ing/secret key signing/etc. is required. And the sequence number passed to the Old REST API is _not_ there to prevent replay attacks - it simply needs to be a number larger than any of the previous messages' sequence numbers (as an attacker, I'd just pass in a very large value; in practice, everyone just passes the UNIX timestamp).
Use tokens issued for a user and IP combination. Use HTTPS to carry the auth for the user and return a token. Use the token with HTTPS or HTTP to continue talking to the server. Expire tokens after some reasonable time. Expired tokens indicate you need to reauth. If you lose a token, it could only be used by someone pretending to be you (and with your IP), so limit what a token can do via the service's API if you want.
Additionally, keeping a user's clear text password in a local datastore is usually a 'bad idea'. At least store the MD5 or SHA-2 of the password (MD5 is considered insecure now though) and then pass the hash along to auth the user before giving them a token.
Yes, that's basically the way to do it. If you're doing it on a mobile phone you can even add HMAC (via SHA-1 or SHA-2, MD5 is still ok for that but we all know it's possible to produce MD5 collisions now) on that token when you're talking on HTTP. That way, all messages on the network will be at least authenticated.
The IP checking bit is probably not a good idea. A mobile phone user can be switching between 3G and a public Wifi hotspot as he goes. It can negatively affect user experience.
