The current Android Compatibility Definition Document 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.]
