I agree that regex is a bad idea -- so is blindly plugging in values to a query. If you were using PDO or mysqli, you can simply str_repeat a "?" pass in the query equal to the number of values in your $skills array.
$statement = $db->prepare('
SELECT * FROM table_name
WHERE' . str_repeat(' skill regexp ?', count($skills))
Simpler, smaller, cleaner, faster. I really like PDO... especially since doing a prepare/exec means the values are sanitized ahead of time.