Simple Feed
To publish a location you can use the place parameter in the /user-id/feed API. The place parameter be the page-id of that place.
For eg: If I want to publish a location: Gurgaon-
\POST /me/feed
place: 106487939387579
and the post will look like:

Earlier you were also able to use this with the coordinates parameter that include longitude and latitude but this is now deprecated. For this you have to use the Open Graph Story- the same that Foursquare is using. That makes the story beautiful and more interactive. "{user} checked in {action} at {place} on {AppName}"
Open Graph Story
Here is explained how to tag places using the Open Graph Actions. (search for Tagging places in the link).
In you meta tags you have to set the location as-
<meta property="place:location:latitude" content="37.416382">
<meta property="place:location:longitude" content="-122.152659">
(Note: The popup dialog that appears after clicking on the image is default be facebook, whenever a place is published. So don't worry about that)
Hope it helps. Good luck!