Just paste this in your template where you want the box to appear:
Code:
<form name="form1" method="get" action="profile.php">
<p>
<input name="user" type="text" id="user">
<input type="submit" name="Submit" value="Find User">
</p></form>
That will make a search box where the user can type in a profile name and then it will go to profile.php?user=username. :)