  We address the problem of identifying remnants of satellite galaxies in the
halo of our galaxy with Gaia data. The remnants have to be extracted from a
very large data set (of order 10^9 stars) in the presence of observational
errors and against a background population of Galactic stars. We address this
issue through a numerical simulation of the Gaia catalogue with a realistic
number of entries. The Galaxy model includes separate light distributions and
kinematics for the bulge, disc and stellar halo. Our catalogue contains
3.5x10^8 stars. We perform tree code 10^6-body simulations of satellite dwarf
galaxies in orbit around a rigid mass model of the Galaxy. The shrinking
satellite cores and tidal tails are added to the Monte Carlo simulation of the
Gaia catalogue. When combining the Milky Way and dwarf galaxy models we include
the complication that the luminosity function of the satellite is probed at
various depths as a function of position along the tidal tails. The combined
models are converted to a synthetic Gaia catalogue using a detailed model for
the expected astrometric and radial velocity errors, depending on magnitude,
colour and sky position of the stars. We explore the feasibility of detecting
tidal streams in the halo using the energy versus angular momentum plane. A
straightforward search in this plane will be very challenging. The background
population and the observational errors make it difficult to detect tidal
streams as discrete structures in the E-Lz plane. The propagation of
observational errors leads to apparent caustic structures in the integrals of
motion space that may be mistaken for physical entities. Any practical search
strategy will have to use a combination of pre-selection of high-quality data
and complementary searches using the photometric data from Gaia. (abridged)
