How to design a schema to store search keywords
First, let me address your concern about data redundancy. I agree with you that the second schema is more likely to reduce the redundancy, and is probably closer to what I would go with. One thing to be aware of, though, is this will be unique search terms. So unless you have some way of normalizing data, misspellings will get through and be viewed as different search terms.

Also, I would switch the way you link the searchTerm to the date searched, so that dateofSearchTerm links to the search term (not the other way around).

CREATE TABLE SearchTerm (
 ID             INTEGER         PRIMARY KEY AUTOINCREMENT NOT NULL,
 SearchTerm     VARCHAR( 255 )  NOT NULL,
 Hit           INTEGER         NOT NULL,
);


CREATE TABLE DateofSearchTerm (
 DateID         INTEGER         PRIMARY KEY AUTOINCREMENT NOT NULL,
 searchID       INTEGER         NOT NULL,
 Date           DATE            NOT NULL
);


It would also be a good idea to make searchID a foreign key that references searchTerm.ID to ensure there are no orphan rows (rows in DateofSearchTerm that do not have a matching parent in SearchTerm). 

As for your anecdotal story about your friend, the biggest thing I see you missing in your designs are indexes. A table 3-million strong should have no problem running quickly with proper indexes.

Using your design, you would want an index on the searchTerm.searchTerm column, and on DateofSearchTerm.date. 

I think if you follow the advice to make searchID a foreign key, that will also become a proper index. I don't use SQL Server, so I don't know if foreign keys require an index, so make sure that it does.