Nyquist frequency - Sampling theory
Both.  For baseband sampling (thus using only low-pass filtering), a sampling rate over over 2x the highest frequency is necessary.  For band-pass under-sampling, sampling at a bit over twice the bandwidth will work, as long as you remember the original band and don't fold (alias) the given band onto itself.  1000 Hz sampling will fold and invert a (slightly narrower than) 500 to 1000 Hz signal down to 500 to 0 Hz, and thus the signal won't be aliased with itself, but with an empty frequency band (after band-pass filtering stuff out, if needed).  Thus, no information will be lost (aliased), as long as you remember the original frequency band (e.g. it was not baseband).  Reconstruction may require a band-pass anti-aliasing filter, rather than a low-pass anti-aliasing filter.  Using knowledge of the original band, you can de-invert and upconvert the samples back to the original lower side-band of a 1000 Hz carrier, for example.