Assumption:  you have all products in PrestaShop store and on all listings on ebay. Now you need to connect both marketplaces.

Solution:
The first step, please import all listings into Catalog->ebay->Ebay Listings.

Some of the imported listings will automatically connect to PrestaShop products, some of them not. Listings that don't have PrestaShop product connection you can manually set product id.

Next step will be created Selling Profiles and Selling List. 
More information you can find in page http://prestabay.involic.com/manual/

In a few words.
Selling Profile should have all ebay listings details information. Like the title, description, category, store category (if you have it), condition, shipping, payment, return policy, etc.
Ebay category details with Item specify you can define in Category Mapping. There you need to tell with ebay category use for selected PrestaShop categories.
Then this mapping you can use in Selling Profile.

After you finish the creation of Selling Profiles & Category Mappings, you can try to create Selling List. In Selling List, you put PrestaShop product and then list it on ebay.
Please create a couple of Selling Lists.

Then Back to Ebay Listings page. On this grid, you can move ebay listings into Selling List.

Please check screenshot - http://screencast.com/t/RiC5NsrGYqh  there you can see where this option located.
Move all needed ebay listings into corresponding Selling List.

After moving listings, all your products will be synchronized to ebay. The order will be imported, Stock level is synchronized.

Please notice PrestaBay use PrestaShop as a primary source for your products. On revise,/relist PrestaShop product data will replace all information.
Please also notice that ebay does not allow change values for all listings data. So some listings still will need to do stop & list to handle it correctly by PrestaBay.