When a user posts a status update on a non-mobile device they have the option to enter a location.
However, I do not see this location information returned in the statuses API or the checkins API. The statuses API has the update info, but not the location information.
Is this accessible?
Not with the public API. If your solution requires it, I would suggest your company pursue becoming a Facebook partner to gain access to the private/custom APIs.