Within the next several years pulsar timing arrays (PTAs) are positioned to detect the stochastic gravitational-wave background (GWB) likely produced by the collection of inspiralling super-massive black holes binaries, and potentially constrain some exotic physics. So far most of the pulsar timing data analysis has focused on the monopole of the GWB, assuming it is perfectly isotropic. The natural next step is to search for anisotropies in the GWB. In this paper, we use the recently developed PTA Fisher matrix to gain insights into optimal search strategies for GWB anisotropies. For concreteness, we apply our results to EPTA data, using realistic noise characteristics of its pulsars. We project the detectability of a GWB whose angular dependence is assumed to be a linear combination of predetermined maps, such as spherical harmonics or coarse pixels. We find that the GWB monopole is always statistically correlated with these maps, implying a loss of sensitivity to the monopole when searching simultaneously for anisotropies. We then derive the angular distributions of the GWB intensity to which a PTA is most sensitive, and illustrate how one may use these principal maps to approximately reconstruct the angular dependence of the GWB. Since the principal maps are neither perfectly anisotropic nor uncorrelated with the monopole, we also develop a frequentist criterion to specifically search for anisotropies in the GWB without any prior knowledge about their angular distribution. Lastly, we show how to recover existing EPTA results with our Fisher formalism, and clarify their meaning. The tools presented here will be valuable in guiding and optimizing the computationally demanding analyses of pulsar timing data.