First off, we need to point out that Wolverine has worked with the Avengers, or members of the Avengers at many points in the past.
But Wolverine officially becomes a member of The New Avengers during the course of events spanning The New Avengers #5 and #6.
The first story arc of the series deals with a number of escaped villains. Wikipedia explains:
The team's first mission is to capture the remaining super-powered criminals who escaped during the riot. The unexpected emergence of an unrelated team of youthful heroes, the Young Avengers, is also a matter of concern. There is also a growing sense of unease with S.H.I.E.L.D. after the disappearance of its leader, Nick Fury. The New Avengers travel to the Savage Land to capture the reptilian mutant Sauron, encountering resistance from the Savage Land Mutates (led by Brainchild) and a rogue squadron of S.H.I.E.L.D. agents led by Yelena Belova. During this conflict, Canadian mutant Wolverine joins the team (while maintaining concurrent membership in the X-Men). The group also recruits the Sentry, a powerful hero who erased all memory of his career from the world after he was manipulated by the mutant Mastermind and The General.
During the events of issue 5, the group of Avengers encounters Wolverine in the Savage Land. Wolverine assists them on their mission. As they finish, Iron Man realizes that Wolverine is the missing ingredient needed to complete the team.
When they are alone, Iron Man tells the team that there’s another problem. The SHIELD files given to them about the Raft had been tampered with, so he compared them with the files from the old Avengers database. Over a dozen of the prisoners had been declared legally dead, yet still imprisoned. This meant that SHIELD was not only stockpiling super-weapons, they were stockpiling super-villains. Whoever is behind it knows the Avengers are onto them, but the Avengers don’t know who they are. Even if they do nothing, the real bad guys know they know something. Cap offers anyone the option of backing out of the Avengers now, if they feel they can’t handle it. Tony then offers a spot to Wolverine, which makes Cap want a private word.
IRON MAN: Cap, you said this team came together by … fate. Your word. Just like the original Avengers, right? Yes. Well the original Avengers didn’t truly come together until that one last ingredient came into the mix. We needed that one last ingredient. And then when we found you … you were that one thing. But for this team, for this situation, for this world … he is you. He is our missing ingredient.
CAPTAIN AMERICA: Tony, he’s a murderer.
IM: He’s a samurai warrior. After what happened to Wanda, after what we know happened here today, we can’t afford not to have him. We’re going to need someone to go to that place that we can’t. And you know exactly what I mean.
Cap reluctantly agrees to allow Logan a spot on the team