Is there a good utility to find files when you have no idea exactly where they are? Secondly what does Linux use for wildcard chars in a search, for example in Windows you use * or ? , is it the same in Linux?

Wildcards:
* matches any number of chars, including none.
? matches one char.

The utilities to find files:
locate: requires an up-to-date database, which is built by the command updatedb. Then, if you know a string of letters of the filename (a regular expresion, or regex), the command is 'locate <string>' for a case sensive search for that string, and 'locate -i <string>' for a case in-sensitive search.

find: If you know part of the filename or part of the contents of the file, use the find command, and pipe it through grep to search in filenames and file contents.
find / -type f | grep <string>, where / begins the search at the root of the filesystem. You can reduce the search by giving the directory to search, as in 'find /home -type f | grep <string>' to restrict the search to the /home directory.
find / -type f | grep -i <string>, does the same except the search is case in-sensitive.

In the examples of find given above, the find command is piped through grep to search for the string.

For both commands, see the man pages: 'man locate' and 'man find' for more information.

I would add a small clarification. There are two types of wild cards. The ? and * characters are used in the shell and for the -name argument of the find command. For real regular expressions ( used in grep, locate --regex, sed, etc. ) the dot (.) character is used instead of ?, and the * metacharacter means zero or more instances of the preceding charactor (or regular expression).

Since the dot character is a metacharacter it needs to be escaped if meant literally as in the above example "/usr/.*gawk\.pdf$'

See the find info manual for numerous examples of using the find command and of regular expressions. There is also a "man 7 regex" manpage.

Will find search all the directories, or only the one you are in when you run it?

Its recursive ie all dirs under the specified one (plus inside the specified one)

You can use the '-maxdepth 1' argument to control the levels of recursion (to 1 in this case). It seems like you haven't read the find man page yet. That will answer a lot of questions. The find command may be the most useful command you will use.

frank@c-75-75-174-33:~$ updatedb
bash: updatedb: command not found
frank@c-75-75-174-33:~$ man locate
No manual entry for locate

Normally you need to be root to run updatedb. Most of us have it run as a cron job.
But...It looks as though you do not locate installed
Consult your packagemanager. For my distro, locate comes as part of the findutils package

Thanks
I'm trying to on Debian forum right now, Got inpatient and tried this forum.