Before I start I want to make sure you are doing everything right. When 1 of you host a game, another person should see his server in internet Server list. If he doesnt he can try checking LAN server list (for this purpose choose in game settings "Connection type: LAN") and hit new list. This is what you do if you dont see it:
Ok I guess you 2 are separated by some distance (I many be wrong so let me know), so this is not "home network problem" even if it is the solutuions explained in this post will work. in this case you 2 have the same problem as most of people. Your routers are blocking your game ports (I dont know what game you are talking about, but it doesnt really matter. most of them work in the same way). If this game is LOSV, then you need to open these ports:
60001 UDP
60002 UDP
13242 UDP
You must allow incoming connections as well. if you are abe to do this your server should appear in Server list (note that it is enough for 1 of you to do this. and then the same person can host online server).
If you dont know how to do it (if you want I can talk about it further, explain how to do it etc. again let me know) there is another way arround and in fact more simple way. You 2 want to play alone, in this case LAN connection is the best solution. Most of people use "Hamachi" program for this purpose. Thats a free, small program that helps to connect 2 pc via LAN through the internet (it makes PC's think that They are using LAN). I also have it and I know that it works. You can download hamachi it here (hit "Download from this server (2.71Mb)" to start downloading). (you both have to download and install it. it is quite simple to use it, but if you have any questions, let me know and we will solve it ). SO in case you done it, all you need to do is to connect each other via hamaci network (it is explained during installation, if not... I can help lol... let me know) , the go to that game, host LAN server (If you are playing LOSV then it doesnt matter, simply host a game). Then the other guy has to launch his game, go multiplayer, hit LAN servers button. normally he should see your server and be able to join. sometimes he cant see it, but there still is a posibility to join a server without seeing it. All you need to do is to coppy hamaci IP and pase it into your game's IP field and hit join button (again I can explain this in more detail if you need). 99% hamachi is the best choice.
I know it a damn long post but I need extra info to make shorter. so let me know what you have done and where you are stuck.