Como fazer para criar elementos html via javascript?

Usando o padrão do javascript, esse é o código para criar uma div e um link, com atributos, e inserir o link na div:

var div = document.createElement("div");
div.setAttribute("id", "minha_div");
div.className = "minha_classe";
var a = document.createElement("a");
a.setAttribute("id", "meu_link");
a.setAttribute("href", "meu_link.htm");
a.setAttribute("title", "meu título");
a.className = "minha_classe_link";
a.innerHTML = "link!";
div.appendChild(a);

Com a prototype, é possível usar uma sintaxe mais amigável; existe a classe Element. Com ela, você pode criar um elemento da seguinta forma:

new Element(tag[, {atributos}]);

O código acima ficaria da seguinte forma:

var div = new Element("div", {id:"minha_div", "class":"minha_classe"});
var a = new Element("a", {id: "meu_link", "class":minha_classe_link", href:"meu_link.htm", title:"meu título"}).update("link!");
div.update(a);

Simples e fácil!