I am not sure the game supports it at all. Have you tried setting the resolution to 1920x1080 with regedit? Its still not all smooth edges, but it looks quite good for a game its age that way, and I am only using software rendering.

You should be able to force AA through your video card control panel.

I did that and it doesn't work. :(

I have installed the game both in my laptop and PC.

In my laptop (ATI mobility radeon 5470 outdated drivers from 2010), I just have to force AA from the Catalyst Panel to get it.

In my PC, with an ATI HD3850 (last drivers from July 2012) that way doesn't work and I am not able to get antialiasing.

If you're using the hw patch, hit Win+r to open the run dialog, type '%APPDATA%/GOG/DungeonKeeper2/config.ini', (without the ') and underneath the LowZBuffer line, add 'Antialias=12'. (Again, without the ') If that gives you a black screen, you can try Antialias=1 instead. It only antialiases the 3d portion of the screen, not any of the overlay.