ExpressionEngine doesn't really need to come into this. Try using HTML5's geolocation API. The success of this approach will depend on the visitor's browser. For instance, Chrome will be using Google's location data which is, as you'd imagine, pretty good and can fall back to use things such as your WAN name to locate you.
http://html5doctor.com/finding-your-position-with-geolocation/
Otherwise you'll need a database of IP ranges vs their location. This is, at best, going to be no more reliable than the HTML5 Geolocation API as it will only show the location of where my 'node' pops up and joins my ISP's backbone.
For instance using an IP to location service (IP2Location) my current location is shown as being about 100 miles from where I actually am - in the UK that's a big deal. A similar demo using HTML5 Geolocation shows the actual road I am on.
Here are some sample IP location bits http://www.iplocation.net/
For a store locator you wouldn't go far wrong using Objective HTML's Google Maps for ExpressionEngine add-on. It's ideal for that sort of thing.
So, to summarise, I would use a combination of HTML5 Geolocation API and feed the resulting lat/lon into GM4EE.