Wild Windsown Weeds are seen with a minimum Exp * Perc score of 75, so odds are you're going to need at least 8 Exploration (unless you've gotten lucky with some early perception). An alternative option is to ask, trade, or steal seeds. There's a lot of abandoned farms around. If you go with the latter, at least replant so that the next guy coming by can get some seeds, too.
The skills needed for farming can be found on the RoB wiki:
http://ringofbrodgar.com/wiki/FarmingThe problem is this: you're probably going to want a claim before you start any farming. Yeomanry requires farming, so you'll have to balance early food issues (exploration for foraging) with getting a claim up. The balance is up to you. I prefer to get just enough exploration to feed myself regularly and then get a claim.
It's been a while since I've read through it, but Sevenless's guide stickied at the top of the forum has a pretty good guide to starting a farm.
Opinions expressed in this statement are the authors alone and in no way reflect on the game development values of the actual developers.