Has anyone done it on their site? I was thinking about it but wasn't sure how to start. It seems Google has an integrated one but it would be nice to make your own, just to search local pages.

Yep

Where to start depends on how you site is coded and what code you can use.

__________________
And how can we win, when fools can be kings

Do you know any sites I can read more about it at? I basically just use regular php to display pages, I could get log-ins to work (most of the time) and news etc. (most features CMS have) but search is one thing I can't get my mind around.

Take a look at Sphider or PhpDig

__________________
And how can we win, when fools can be kings

You can start by building search algoritms which can search basic keywords first. Then you can start indexing pages based on the keywords. If possible use PostgreSQL as the database, it is much faster than MySql.