Very good question! The TDD/BDD way would suggest you take the user stories and write validation points (read high level tests). They use GWT (Given/When/Then) speak as follows.
"As A User I should be able to Search for more users so that I can add more friends on the website"
given the website URL
when the site loads
then a search field should be visible/accessible.
This is your first piece of feedback and first opportuniuty to iterate with the product owner. Ask questions like where should the search bar go? Should it auto complete? Etc. Next you assign "behavior to the UI objects. These also have validation points.
This would define the behavior of the search button:
given a go button next to the search field
when then button is clicked
then a search should be performed
this would describe the logic of your search:
given a search term "John" and a user set including "John, Joan, Jim, Steve"
when a search is performed
then the results should contain "John" an "Joan"
The first validation point would describe the behavior of linking the controller search button to an arbitrary model implementing the search algorithm. The second validation point describes the search algorithm itself. The advantage is that these pieces are defined independently and can be designed in parallel. It also gives you a nice API and small easily to plan features to iterate on. It also gives you the ability to iterate/refine on any piece of the puzzle without affecting the rest of the pie.
Update I also want to mention that what I refer to as validation points can loosely be associated with UATs or User Acceptance Tests. Don't get hung up on the terms because they're irrelevant. Focus on the idea behind them. You need to take the user story and break it down into specs. (can be done in one or many passes using either UATs or validation points or both or magic beans just make sure you break them down.) If what you have broken your user stories into can be written in a tool like FitNesse, JUnit, or RSpec then use one of these tools, other wise you need either further conversation (Are your user stories too vague?) or another pass over what you have to break down further (UATs to validation points). Don't obsess over the tools and feel like you need to automate everything from the beginning. Leave Selenium alone until you get the manual process down. Eventually you want specs that can be written in programmatic test-like form at this time you should be able to use something as simple as JUnit to start coding. When you get better/fancier you can pick up EasyB or RSpec story runner and other things.