module.paths stores array of search paths for require. Search paths are relative to the current module from where require is called. So:
var fs = require("fs");
// checks if module is available to load
var isModuleAvailableSync = function(moduleName)
{
    var ret = false; // return value, boolean
    var dirSeparator = require("path").sep
    // scan each module.paths. If there exists
    // node_modules/moduleName then
    // return true. Otherwise return false.
    module.paths.forEach(function(nodeModulesPath)
    {
        if(fs.existsSync(nodeModulesPath + dirSeparator + moduleName) === true)
        {
            ret = true;
            return false; // break forEach
        }
    });
    return ret;
}
And asynchronous version:
// asynchronous version, calls callback(true) on success
// or callback(false) on failure.
var isModuleAvailable = function(moduleName, callback)
{
    var counter = 0;
    var dirSeparator = require("path").sep
    module.paths.forEach(function(nodeModulesPath)
    {
        var path = nodeModulesPath + dirSeparator + moduleName;
        fs.exists(path, function(exists)
        {
            if(exists)
            {
                callback(true);
            }
            else
            {
                counter++;
                if(counter === module.paths.length)
                {
                    callback(false);
                }
            }
        });
    });
};
Usage:
if( isModuleAvailableSync("mocha") === true )
{
    console.log("yay!");
}
Or:
isModuleAvailable("colors", function(exists)
{
    if(exists)
    {
        console.log("yay!");
    }
    else
    {
        console.log("nay:(");
    }
});
Edit: Note:
module.paths is not in the API 
- Documentation states that you can add paths that will be scanned by 
require but I couldn't make it work (I'm on Windows XP).