HTMLエレメントを取得してstyleで設定

var e = document.getElementById("hoge");
e.style.backgroundColor = "#CCCCCC";

CSSStyleSheetを動的に作る

var style = document.createElement("style");
style.setAttribute("type", "text/css");
style.appendChild(document.createTextNode("")); 
document.getElementsByTagName("head")[0].appendChild(style);
 
var sheet = style.sheet;
// sheet.addRule(".clazzName { color: blue; }");   // IE?
sheet.insertRule(".clazzName { color: blue; }", sheet.cssRules.length);

クラス化すると楽かも（要prototype.js）

var DynamicCSS = Class.create();
DynamicCSS.prototype = {
    initialize: function() {
        var style = document.createElement("style");
        style.setAttribute("type", "text/css");
        style.appendChild(document.createTextNode(""));
        document.getElementsByTagName("head")[0].appendChild(style);
 
        this.sheet = style.sheet;
    },
    appendRule: function(selector, rules) {
        r= new Array();
        for (var i in rules) {
            if (rules.hasOwnProperty(i)) {
                r.push(i + ":" + rules[i]);
            }
        }
 
        rule = r.join(";");
        if (this.sheet.addRule) {
            this.sheet.addRule(selector + "{" + rule + ";}");
        } else {
            this.sheet.insertRule(selector + "{" + rule + ";}", this.sheet.cssRules.length);
        }
    }
};

参考：Safari で CSSStyleSheet オブジェクトを生成する方法 - IT戦記