The [current Android Compatibility Definition Document][1] says:
> ### 7.3.3. GPS 
> Device implementations SHOULD include a GPS receiver. If a device implementation does include a GPS receiver, it SHOULD include some form of "assisted GPS" technique to minimize GPS lock-on time.

So "SHOULD" does not mean "MUST". *[Edited because I messed things up. Apps that require GPS show up in the market regardless of whether the device supports it or not.]*

  [1]: http://source.android.com/compatibility/2.3/android-2.3.3-cdd.pdf