Should I get a size up or a size down bike? I'm looking to buy a Trek DS 4 bike. In the store the sales person measured me and said I'm right in between sizes 19 and 21 and he wasn't sure which one I should pick. I test drove both sizes and didn't feel any difference, though I have only spent a few minutes on each and I suspect the differences would show themselves on a longer ride (like how tired my back and hangs get etc).

Any recommendations on which way (size up or size down) to go for more comfortable/efficient rides?
I would be cautious of any blanket advice suggesting that everyone should make the same decision. Whether to size up or size down depends on a number of factors:


How you ride (e.g., relaxed or aggressive)
Your flexibility
Your body proportions
Your fit window (range of fit positions you find comfortable)
Availability of components to modify fit (e.g., stems)


Many will suggest that you size down when in doubt, this likely comes from observing that professionals (e.g., road riders) tend to use smaller frame sizes.  This is done to get the rider in a more extreme aerodynamic position, these positions are generally not that comfortable and not advisable for most riders (remember the pros have access to daily physio sessions to constantly undo the effects of these positional contortions).

Ideally, you should be looking at your body proportions when making this decision. For example, I personally have longer legs, shorter torso and longer arms than average (BTW - no average person exists).  While my legs are longer my femurs are relatively shorter (i.e., lower legs are relatively longer). This puts me a bit taller and forward on the bike as such a frame with more stack (i.e., size up) tends to work better as long as the frame's reach dimensions are reasonable. My slightly longer arms means I tend to use standard stems. For frames with longer reach geometries this may not work out however work out as well.

Below is a good summary of how short/long legs impacts your proportions and therefore whether you may want to size up or down.


  Bike Sizing Guide - Road Bikes
  
  Short legs
  
  Short legs will also mean a long torso, so there is danger of the rider being too hunched up on a height suitable bike. The short legs will also mean a lower saddle height, so the distance between saddle and bars is reduced anyway. With a bit of luck, the short legs may also mean short arms which would balance out the long torso! The biggest danger here is selecting a bike based on top tube length i.e. larger than normal for overall height, but then suffering from cranks that are too long. A better compromise may be the use of a longer stem.
  
  Long legs
  
  Sorry for all these long legged people, but this is the worst case for achieving an optimum bike fit. The long legs will mean a high saddle, so the bars become relatively far away. Long legs imply a short torso, so the reach to the bars becomes excessive. One could consider a shorter top tube, but this would also tend to come with a shorter head tube which is counter-productive. What tends to happen with very long legged people is that stems have to be short and as high as possible, often achieved by flipping them over as well as using all the available spacers. In many cases this is still not enough and the saddle also has to move further forwards than is ideal. Many people do not like the aesthetics of this stem configuration, in which case the best option is to select a bike with Sportive or Touring geometry, i.e. one with relatively long head tube or Stack for its size.


Therefore if all else is equal, short legged people would want to size down and then select a long stem, while long legged people will want to size up then select a shorter stem. All of this gets further confounded by other issues you may have such as poor flexibility, back pain (you typically need to be more upright) and how you want the bike to handle (longer stems slow the handling a bit). 

In short, there is no one size fits all advice as to whether you should size up or down.