j123 ... issue seems to be your understanding of regular expressions.
In your example:
123456 mon MAR 17 13:00 2006
You can do grep "mon MAR" as these words are side by side in the file so it will find them accordingly.
However, MAR and 2006 are not side by side so you need to tell grep about the fact that there might be
something else in between, hence you would need to do:
grep "MAR.*2006" file
This says, look in the file until you find the word MAR and then look to see if after zero or more
of any other character(s) that the characters 2006 appear. If yes, return line
Obviously now you need to ask yourself, to what level will you allow the users to enter data?
ie, single word only, words separated by space, regular expressions, ...