Recently hired to build links? Ouch! You've kind of jumped right into the fire...
What StevieD and Ultimate said is accurate. But there is some light at the end of this dark tunnel.
From what I read and see, brand new sites are having an easier time ranking quickly with a fairly small link collection. It's a glitch with Google loving fresh content, but the glitch don't last long because soon you aren't so fresh anymore.
So forget about getting 1000's or even 100's of links. Think about getting just a couple dozen really good ones. Fortunately you already have a blog on site, because your going to need it.
How to get them? Depends on what your site is selling, and what your blog is about. You're going to have to talk to people by email, on forums, by twitter, and even by phone. Try to find compatible (not competing) stores make a deal to write a how-to type article specifically for them that contains an appropriate link back to your site. Let a few of the right folks do guest posts on your blog in exchange for help getting a link on another site or in another blog post they are working on. Participate in Google+ since it is a good place to occasionally (rarely really) get links to your pages or posts. And it is a great place to network with others in your uncomfortable shoes.
It would help if we had a clue what sort of stuff your store sells. Housewares, car parts, DVDs, what?
Checking out the link profiles of your good competitors is another way to get ideas for where to get links. Focus on the "follow" links.