Executive Summary
You can negotiate anything. The more leverage you have, the more you can negotiate.
In this case, your leverage depends on three things:
- What you've already agreed to
- How badly they want you
- How willing you are to walk away if you don't get what you want
Prior Agreement Kills Leverage
The more you've already agreed to, the less wiggle room you have. For instance, if the company discussed salary with you already, and you've accepted the job, there is an implication that you were content with the salary if you didn't say anything at the time.
In the case that you've already signed a contract, there is virtually nothing you can negotiate since you have to overcome the hurdle of already having an agreement in place before you can negotiate a new one.
Need is Strong Motivation
If you are the only person in the world who can do what you do, you have a lot more leverage than if you're easily replaceable. If Yo-Yo Ma agrees to play cello at your concert, you are going to have a tough time replacing him, so you are going to be more willing to give him more leeway in any negotiation.
Think about your value to this company compared to other options. This means understanding your market value (how much they'd pay for someone of similar talent), and understanding the pool of talent (how easy it is to replace you for that much). If you are asking for more than market value with a good supply of talent, you are going to have less success than if you are asking for a bump to market value with a smaller pool of talent.
Walking Away
If you aren't willing to walk away with nothing if you can't negotiate what you want, then you aren't going to have much luck negotiating. Most people in your situation (first job, already agreed) aren't willing to give up a job in hand for a small bump in salary or perks, because the fear of unemployment is a far more powerful motivator than whatever they think they have to gain from the negotiations.
Think long and hard about how willing you are to sacrifice everything they're offering for a little more, based on what you've already agreed to and what your market value is. If you have other options if this falls through, and those options can be kept open, it's a lot easier to negotiate than if you've already turned down all the other offers and turning this job means you have to re-start the search.