Well, as for saving the search and results, that's just typical logging as dagon said. You can use a text-file, xml, or even a couple tables in the database to save the info 😉 Whichever you prefer and works out for you.
As for knowing what link was clicked, here's a good spot for sessions/cookies. You can set a session variable (like "referrer") and give it the value of say the search "id" 😉 Then on every page you check to see if $_SESSION['referrer'] is set. If so, log it as a "click-through" from your search; otherwise, ignore it and move on.
That's much more reliable than using $_SERVER['HTTP_REFERER'] since not all browsers are going to send it (since it's not required). So using a session and setting your own "referrer" code would be best. Obviously you'd clear it out once they've hit the next page.
Alternatively if you're looking for a type of "ranking" scheme for search results, you could do what many large sites do and ask the user if the returned result was helpful to them or not. Let them answer either yes or no, or on a scale from 1 to 5 or something and then calculate a % based on <helpful>/views. So then you can rank it in order of "helpfulness" 😉