Doing locking in ASP.NET correctly

Unless you're absolutely certain that it's critical to have no redundant queries then I would avoid locking altogether. The ASP.NET cache is inherently thread-safe, so the only drawback to the following code is that you might temporarily see a few redundant queries racing each other when their associated cache entry expires:

public static string DoSearch(string query)
{
    var results = (string)HttpContext.Current.Cache[query];
    if (results == null)
    {
        results = GetResultsFromSlowDb(query);

        HttpContext.Current.Cache.Insert(query, results, null,
            DateTime.Now.AddHours(1), Cache.NoSlidingExpiration);
    }
    return results;
}

If you decide that you really must avoid all redundant queries then you could use a set of more granular locks, one lock per query:

public static string DoSearch(string query)
{
    var results = (string)HttpContext.Current.Cache[query];
    if (results == null)
    {
        object miniLock = _miniLocks.GetOrAdd(query, k => new object());
        lock (miniLock)
        {
            results = (string)HttpContext.Current.Cache[query];
            if (results == null)
            {
                results = GetResultsFromSlowDb(query);

                HttpContext.Current.Cache.Insert(query, results, null,
                    DateTime.Now.AddHours(1), Cache.NoSlidingExpiration);
            }

            object temp;
            if (_miniLocks.TryGetValue(query, out temp) && (temp == miniLock))
                _miniLocks.TryRemove(query);
        }
    }
    return results;
}

private static readonly ConcurrentDictionary<string, object> _miniLocks =
                                  new ConcurrentDictionary<string, object>();

Your code has a potential race condition:

if (HttpContext.Current.Cache[query] == null)         
{   
    ...
}         
else         
{
    // When you get here, another thread may have removed the item from the cache
    // so this may still return null.
    results = HttpContext.Current.Cache[query].ToString();         
}

In general I wouldn't use locking, and would do it as follows to avoid the race condition:

results = HttpContext.Current.Cache[query];
if (results == null)         
{   
    results = GetResultsFromSomewhere();
    HttpContext.Current.Cache.Add(query, results,...);
}
return results;

In the above case, multiple threads might attempt to load data if they detect a cache miss at about the same time. In practice this is likely to be rare, and in most cases unimportant, because the data they load will be equivalent.

But if you want to use a lock to prevent it you can do so as follows:

results = HttpContext.Current.Cache[query];
if (results == null)         
{   
    lock(someLock)
    {
        results = HttpContext.Current.Cache[query];
        if (results == null)
        {
            results = GetResultsFromSomewhere();
            HttpContext.Current.Cache.Add(query, results,...);
        }           
    }
}
return results;