Use the LVL (License Verification Library) provided via Google, its a server side verification that the user actually bought your app.
http://developer.android.com/guide/market/licensing/index.html
Use other techniques to detect if you application has been tampered with, there are a few and they are covered in this blog post and the I/O video. Assume it was pirated if tampered with. (Double extra check to make sure you don't mess this up and annoy real users)
http://android-developers.blogspot.com/2010/09/securing-android-lvl-applications.html
http://www.youtube.com/watch?v=TnSNCXR9fbY
Use AntiLVL against your own application, attack it like a cracker! This is actually really fun and educational, see how much work it takes to crack your app. The blog/tool go over the known weaknesses and you can make some educated decisions about how to stop the automated tools from working. Stopping dedicated pirates is no ones priority, but stopping people from using a 1-click tool is easily obtainable.
http://androidcracking.blogspot.com/
EDIT 1:
Make a free version with ads and/or less features. Crackers just want free stuff, so make it easy on them :) If you detect they are using a cracked version of your paid app you can try and convert them to using the free version or upsell them to the paid version. Currently about 1/4 of the people cracking one of my apps will open the Google Play for the full paid version (although less actually buy it)