We consider the problem of a user searching for information over a sensor network, where the user does not have prior knowledge of the location of the information. We consider three information search strategies: i) a ource-only search, where the source (user) tries to locate the destination by initiating search which propagates as a continuous time random walk (Brownian motion); ii) a source and receiver driven "sticky" search, where both the source and the destination send a search or an advertisement, and these leave a "sticky" trail to aid in locating the destination; and iii) where the destination information is spatially cached (i.e., repeated over space), and the source tries to locate any one of the caches. After a random interval of time with average t, if the information is not located, the search times-out, and the search is unsuccessful. For a source-only search, we show that the probability that a search is unsuccessful decays as (log (t))(-1). When both the source and the destination send search packets or advertisements, we show that the probability that a search is unsuccessful decays as t(-5/8). Further, faster polynomial decay rates can be achieved by using a finite number of searches or advertisements. Finally, when a spatially periodic cache is employed, we show that the probability that a search is unsuccessful decays no faster than t(-1). Thus, we can match the decay rates of the source and the destination driven search with that of a spatial caching strategy by using an appropriate number of search packets. The sticky search as well as caching utilize memory that is spatially distributed over the network. We show that spreading the memory over space leads to a decrease in memory requirement, while maintaining a polynomial decay in the search failure probability. In particular, we show that the memory requirement for spatial caching is larger (in an order sense) than that for sticky searches. This indicates that the appropriate strategy for searching over large sensor networks with little infrastructure support would be to use multiple search packets and advertisements using the sticky search strategy.