The general, short, easy answer is - Tell your boss you are looking when you have a new job and are handing in your resignation letter.
The reason is as others have said - there's not much that your boss can do to change that. The thing to talk about with your boss is your current issues, in specific, productive, changeable detail. That's something he can change. If he cares, and if he agrees with the need for change, he'll help to make the changes possible. If he doesn't agree or doesn't care, then he can't really be so surprised when you leave.
The general thought is - keep it positive and productive. Don't hand your boss a problem and hope he can fix it - give some thought as to what would make you happy in this company, and what changes could occur to make that happen. If the answer is "I will never be happy, there is nothing that can be changed" - then just go look for a new job. Even so - there is nothing your boss can do, as he can't change the company if you hate it this much.
The Exception
I have actually violated this general guideline once - and I stand by it. Having kept in touch with the people involved, I can say honestly that it only did good things for my career.
Here's the deal - the one time I would advocate telling your boss early is if you are in a situation where:
- You've hit the final case - there's no reason you would stay. The problems are not fixable.
- You have a very good relationship with your boss, and a lot of trust in the boss' ethics and loyalty to his people.
- Your boss is in a position where the knowledge that you are leaving could influence some critical decision making that is important to the work and the team.
- You feel reasonably sure that a new job isn't all that far away.
It's a real balance, to be sure, because your boss knows more about the business than you do, more about the team than you do, and more about what the strategy will be than you do. And you don't really know if you will get a new job offer tomorrow, next week or next year. Having so little information at your disposal puts you in a pretty weak position.
But I did exactly this at a time where I knew that my skill set was rare, hard to replace, hard to grow and the lack of having me around made certain elements of future work planning particularly difficult or different. The boss was in a tight spot, and in knowing he probably wouldn't have me around in another fiscal quarter could influence him to select certain other senior people for the team so the total project would survive.
I had already turned down one job offer, and had several others stewing, so I knew that my departure was likely.
I told him, he wasn't surprised, and we still have a great relationship - 2 years later we still touch base and keep in contact and I count that as an overall career win. In the long view, having good working relationships with competent and trustworthy people will open doors, so once and a while, the risk is worth it - just make it an educated risk.