If you came here to play HL, HL2 or any other Steam for Linux released game see How can I install Steam? for the answer which is a lot simpler than this. This one only apply to games outside the Steam environment or not yet on steam. Also know that Half-Life is natively supported in Ubuntu. Most likely HL2 will follow.
To play both, HL and HL2 (Not through steam) you first need the Wine PPA (It is much better than the actual version that comes with Ubuntu). So first install the Wine PPA (Does not matter if you already have PlayOnLinux installed). PlayOnLinux can work without the need of having Wine installed since it will eventually download its own version of Wine if it detects you do not have one (Including addons which are similar in use as winetricks). It also downloads specific Wine versions even if you have Wine install for some specific cases (Some games in PoL depend on specific Wine versions).
If you use Wine PPA or PlaOnLinux the game should work with no problem.
Follow this guide to install the latest Wine: http://www.winehq.org/download/ubuntu
After that go to Software Center and look for Wine with version 1.5.x. Right now it is 1.5.23. Install it. You can also install it via the terminal with
sudo apt-get install wine.
Download PlayOnLinux from their website and install it.
Execute PlayOnLinux at least once so it can download the needed Fonts and configures itself for use.
If you try to run the games with Wine, first try to download, any needed libraries and additional packages the game needs. This can be done with winetricks. You can run winetricks from the Dash or from the terminal like
winetricks --gui. For HL, HL2 and many other games I have tested, including but not limited to: Trine, Trine2, Portal, Portal2 and many others I recommend the following Winetricks installation:
Open Winetricks and select Select the default wineprefix
Select **Install a windows DLL or component
Install all that I have marked (and any additional you need for a specific app). This should cover many apps and games. I have not had any additional problems after installing this with many games:
The Physx component, even if you do not have Nvidia, you still need to install it for games that require it.
Now simply right click the installer for HL1 or HL2 and select Open with Wine. Tested again with both games. Working perfectly (Not the Steam version, only the older CD/DVD versions).
If you try to run the game through PlayOnLinux, the app will guide you step by step on how to install the game and will take care of many aspects of it's installation including needed DLL and other components to make it work right.