You can learn lockpicking the same way you increase any other skill. In the skill list on PC, select a skill, hit the arrow button under the icon to add skill points (up to the skill level cap, your available number of skill points and any character level restrictions), and the button at the bottom right of the window to apply.
On the Xbox, in the skill list hit A to show the skill description, and A again to apply skill points; when you hit B to exit you are given the choice to apply the points (A) or cancel (B).
BTW, I did leave a couple chests for later. One of the chests under the church always gives body parts, so I left that chest until I had explored enough of Broken valley to find the crystal skull required to control a necromancer created creature. However, even being at a higher level when I returned, I had still found better stuff by then anyway, so waiting didn't help (then again, in that case getting lower level parts earlier would not have helped either).
Some side quests you just need to explore everywhere, and you will eventually find the person or item you are after. With Brave Sir Robin, the creature you need to defeat is not too far from the quarry (south east of where you meet the dragon knight, then cross the river and south west); you'd probably want to be at least level 11 or 12 for that area/quest.
