I've never even tried something like this but here are a few tips (may be useless ones, though!)
The first thing to look at is how the instant messenger is going to run. There are two different methods. First is the 'ICQ method', where you login through a server and get the IP addresses of all the contact list members. Then, messages etc. are sent directly to the IP address.
The other method is the MSN method, where all messages are routed through the central server. It is really up to you which method to use.
I would recommend using C++ Builder or Delphi to create the actual messenger program. These come with good web interaction which will be vital. They are also visual programming tools which will make creating the GUI better.
On the server you will need some sort of database (MySQL perhaps) and a web server (Apache would be my choice). Then its really all up to you!
I suppose it would work something like this:
1. Client sends logon details to server
2. Server gets client's IP, logs them in to the server, and sends confirmation to a pre-specified port on which the client is listening
3. User's contact list is loaded and data sent to client with details of who is online etc.
4. Server notifies all users who have the client on their list that the client is online
Then to send a message:
1. Client sends message and username to server
2. Server looks up IP of username and sends message to their 'listen' port
Also you would need to send a message from the server to the client regularly and, if it was not replied to by the client software, log them off.
Hope that rambling is of some help
<edit>
You may also want to have a look at some of the projects on SourceForge. There are a cople of messengers (like Miranda (I think)), which might be helpful to you. ICQ also used to provide an API, which you could download and look at.
Another useful thing to look at would be AOL's interoperability document, which described a lot about how AIM works. If you can't find a copy online, let me know as I think I still have one.