Locations are added to Store Locator Plus® via the sidebar menu via the locations submenu. This option presents a list of all locations along with a menu option to add a location via a web form.
If you have many locations and have either the Power add-on enabled for the plug-in or have signed up for the Professional level plan for the mySLP SaaS you can import them via a CSV import file.