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". But if a device does not have GPS and is Android compatible, the market will not show any apps that require GPS.

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