In your store's Admin area, go to the Products section Catalog > Products > Edit Product
Categories: Category or categories where product will be displayed on storefront. Click on Add/Edit button, the popup will appear. Selecting a category will associate this product to that category, and you can select as few or as many associated categories. Click Apply Selection button to close popup and apply changes.
Related Products: offering to customers the products related to the current product when customers are viewing this product.
Set Related in the Grid
Related products can be assigned for any products in Admin > Catalog > Products grid. On this page select products in the list and choose set related in the right bottom of the grid.
Stores: select store where product will be displayed. If you're managing multiple Stores, you can select the stores to which this product is associated by checking the checkbox next to the Stores from which you want the product to be available.
read more about multi-store set up in this article
Even if your product is not assigned to any category or assigned to disabled category it is still available in search, as related product, in data listing blocks (specials, bestsellers) and with direct product link.