Here's a quick summary...
Maps Engine
- Designed for large amounts of Geospatial data
- Geocoding is done server-side
- Import KML, CSV, shapefiles, etc. some support for import from commercial GIS tools
- Supports raster layers, polylines, etc
- Supports rendering to Google Earth
- Table size of "millions of points, lines, or polygons"
- Depending on which Engine used, there's either a great UI for drawing on maps (Maps Engine Pro/Lite) or a more "heavyweight" UI with advanced features.
Most of this data comes from the product page.
Fusion Tables
- Designed for joining tables together (fusing, eh eh)
- Purely free - though experimental - product
- Geocoding is done client-side (so subject to individual quota & throttling)
- Has way more features in Maps API (server-side heatmap, styling, etc.)
- Upload from CSV, KML, or enter by hand
- KML stored in table cells with character limits
- Table size of 250MB max, 100MB optimal (100k row limit when using spatial queries or map layers)
There's lots of useful Fusion Tables info in this question.
I can't really suggest one solution or the other, as it will depend on your specific needs. If you're serious about long-term use of geo data (especially if you already have it in a GIS platform, or have a lot of data) I'd probably use Maps Engine. If you're looking to do some quick visualisations of a "small" set of data (<100k rows) and aren't too worried about the inherent risks of experimental tools, then I'd use Fusion Tables.
Regarding your store locator specifically, the Maps Engine docs describe Best Practices for creating a Store Locator, as well as a video demo.