Hi Samuh,
To address your first question, you should be able to use any Java OAuth library on an Android, here's a link to a tutorial that uses the Java OAuth project library to develop a consumer app on an Android:
Specifically pay attention to the registering of a custom URI scheme (i.e. myapp://) with your application. You'll use this URI scheme when sending the oauth_callback parameter which will allow your users to go through the 3-legged workflow easily (basically you'll get a request token from the SP, direct your user to the SP via a browser to authorize the token, then the SP will redirect the user back to your app using the custom URI scheme).
Now for your second question: When somebody says that a site or service supports OAuth, it usually means that they have implemented OAuth as a Service Provider. This means that you can develop a consumer app that uses OAuth to perform delegated authorization to the protected resources hosted by the service. Be careful to note which version of the OAuth spec the service / site supports. Most should be on 1.0a, but some may still be on 1.0 which has a slightly different workflow. You can safely ignore the differences and just read the 1.0a spec if that's what they support, otherwise you'll want to dig up the 1.0 spec (links provided below).
Let me know if that helps, or if there's anything in particular you'd like me to elaborate on! Good luck with your app!
Note that 1.0 has some security issues that were addressed in 1.0a. Also note that 1.0a has been rewritten as a IETF draft. The terminology used is slightly different in the IETF draft, and some of the requirements have been dropped when using a secure transport layer (i.e. SSL) and the plaintext signature method. Most SPs will still adhere to 1.0a though. Otherwise the IETF draft is much more well written and is worth a read, if you can mind the terminology differences: