In this work, we investigate strategies for training convolutional neural networks (CNNs) to perform recognition on remote sensing imagery. In particular we consider the particular problem of semantic segmentation in which the goal is to obtain a dense pixel-wise labeling of the input imagery. Remote sensing imagery is usually stored in the form of very large images, called "tiles", which are too big to be segmented directly using most CNNs and their associated hardware. Therefore smaller sub-images, called "patches", must be extracted from the available tiles. A popular strategy in the literature is to randomly sample patches from the tiles. However, in this work we demonstrate experimentally that extracting patches randomly from a uniform, non-overlapping spatial grid, leads to more accurate models. Our findings suggest the performance improvements are the result of reducing redundancy within the training dataset. We also find that sampling mini-batches of patches (for stochastic gradient descent) using constraints that maximizes the diversity of images within each batch leads to more accurate models. For example, in this work we constrained patches to come from varying tiles, or cities. These simple strategies contributed to our winning entry (in terms of overall performance) in the first year of the INRIA Building Labeling Challenge.