Users won't signup the very first time they visitimmediately after visiting your site, unless you're someone they know about already.
They need to look around and find your services / products interesting for them to consider following you. And not every user will look for the newsletter sign up so they will have to be reminded that they can get the latest updates through your newsletters.
There are several ways in which you can prompt the user to sign up.
1. Sidebar : Sign up form on the top of the right sidebar.
2. Footer: Sign up block on the footer.
3. Product Pages: Have a signup block visible where ever your products / services are.
4. Lightbox on their first visit (Not-recommended): You can have a lightbox popup where users are prompted to signup for the newsletter on their first visit.
And most importantly instead of saying "Sign up for our newsletter," give them the value proposition (ie. mention what the user will gain from sign-up). Something along the lines of "Sign up to get notified about our latest offers."