From what I understand, there are three major challenges to developing a game for Linux.
The first is using cross-platform libraries. Instead of focusing on DirectX, the developer would need to use libraries like OpenGL, SDL, and OpenAL. While this does take a little more work, most developers nowadays end up using multiple libraries, especially when cross-developing for consoles and PCs. The standard practice is to implement one's own container API, which would be able to use multiple types of libraries and still present the same interface for the game itself. This makes swapping between something like Direct3D and OpenGL relatively trivial, and is pretty much required if a game is being developed for consoles and PCs.
The next challenge is that the game needs to recognize a POSIX-based filesystem. This can be somewhat tedious to implement, especially if some paths are hardcoded into the game (bad practice!), but in the end it would be less work to do than accommodating cross-platform libraries.
The last major challenge is linking the libraries. There are two main methods of linking libraries when compiling a program. One can either dynamically link the libraries, so that the game would use DLLs/SOs to access functions for OpenGL, OpenAL, DirectX, etc, or one can statically link the libraries, so that the game has the code directly built in and has no need for DLLs/SOs. Whereas in Windows, one can simply put the DLLs required in the install directory of the game, on Linux programs aren't installed in their own directory, but rather the components of the game are installed in specific directories. For example, the executable is stored in a bin directory of some sort, libraries are stored elsewhere, and data is stored elsewhere. This means that on a regular installation, the SOs would NOT be installed with the game, but rather installed as their own package and the game would utilize it. The problem comes when the SOs are updated and their interface is changed from whatever interface the game uses. On Windows, the game would continue to use the old, out of date DLL that is provided in the game directory, but on Linux the game would try to use the new SO and would fail due to the changes. Most open-source projects are maintained by the community, so even if the original developer stopped supporting the software long ago and had no intention of updating it to fix the incompatibility, the community can step in and make the changes. This is usually not the case for commercial games.
The solution is to compile the library right into the executable itself. However, that brings its own problems, such as potential security issues, a larger executable, old libraries using resources not available in new versions of the Linux kernel, etc. I'm not familiar with all the solutions to this, but I'm sure there are plenty of ways to do it. (A wrapper class translating old SOs to new interfaces seems ideal to me.)
There are other minor issues that may come into play when developing a game for linux, but these are the major ones that cost the developer the most time and effort. Someone mentioned that different distributions would be an issue, but this is not the case. Granted different distributions use different package managers and installation methods, but the overall method of installing something on Linux is exactly the same for all distributions. The company can either release an installer that automatically builds a package for whatever distribution the game is being installed on (the ATI installer for videocard drivers does this pretty well), or they can make their own shell-script to install the game (which should be fine as long as they provide an uninstaller, as the package manager of the system would not recognize the installation through this method), or they could go the Unreal Tournament 2004 method, where the game is simply copied into the user directory and run locally (this has its own minor issues, the biggest being that the game would only be available to one user unless they did a bit of monkeying, but it still works just fine).
In any case, Valve has already taken care of the first two challenges for their Mac release, and the third challenge shouldn't be a major issue. The only reason I can see them holding back on a Linux release is whether it would be worth the time and effort commercially. One could definitely say that yes, it is worth the effort, especially seeing the statistics various indie developers have posted about releasing games for Linux. The Linux gaming community is growing, and it will continue to grow, so while it may seem small right now, it won't necessarily be this way in the future.
So I'm not sure why Valve would not release a Linux version. Perhaps someone can point out an aspect of Linux game development which I have missed. I'm pretty sure I've covered them all, but I've never developed commercially, so I can't be certain.