With the eBay store, if you select to list as a store item (vs. auction or fixed price, up at the top of the listing page), then you will get pull down menus to pick your store categories. They will shop up right underneath the place where you pick eBay categories.
When I add categories to my store, there is a bit of lag time before they show up on Auctiva.
As far as the Auctiva store, those aren't really categories - they are searches. So you can't really "put" items into those categories. But you define the search terms associated with each category, and then your items end up in the category.
For example, I sell cake pans. So I have defined a category as Cake Pans, put the search terms as "pan", and then when a customer clicks on Cake Pans, it is essentially the same as them doing a store search of "pan", and all the pans show up.
Hope that helps you!
Roxi