What are "goes well with" recommendations based on?
This question is very broad, but yes there are some general principles.


Foods that grow together (geography) or ripen at the same time are often considered to go especially well together. Tomatoes, for example, are more often paired with basil or oregano than they are with other herbs. Pork and apples, for example, are not ready until the fall and grow in the same parts of Europe.
Some meats are richer and fattier than others and are often served with an astringent red wine or an acidic (lemon, wine, vinegar, ...) sauce for contrast. This doesn't just make the food taste better, it's often more important the effect on how the wine tastes after eating different foods.
Some proteins (such as fish) are softer and less chewy or crunchy than others, so they're often served with a crunchy starch - French fries instead of mashed potatoes, for example - or vegetable (coleslaw made with raw cabbage) for texture contrast. Others are chewy so they're served with mashed potatoes, again for a texture contrast.
Some fish is light and delicate while other fish is stronger and oilier. You would use a different sauce with each and drink a different wine with each.
Some combinations are traditional and people enjoy them whether there is science behind them or not - we put butter on mashed potatoes and sour cream on perogies, but there's probably no good reason we couldn't switch those pairings, for example. 
Some foods have more flavor than others and can stand up to a strongly flavoured sauce or drink. This is probably why people make pepper-crusted steak, but not pepper-crusted chicken. Some need to be enhanced by adding more herbs, spices and other flavourings.


Generally the recommendations come from either experiencing that exact combination (until you've tried ground black pepper on strawberries, you just will not imagine that it could be good, but it is) or from experiencing half of it - this sauce was great on that cut of beef, I think it would be even better on a particular cut of bison (because I know the similarities and differences in the meat and can imagine that combination.) The more different kinds of food you eat, and the more you think about what you're eating and why it's yummy or not, the better you will be at knowing the likelihood a particular combination will be good.