Ok, try that:

var opt = document.createElement("option");

var content = document.createTextNode("PU (unrated)");
opt.appendChild(content);

var attr = document.createAttribute("value");
attr.nodeValue = "pu";
opt.setAttributeNode(attr);

var targetEl = document.getElementById("lobby-format");
targetEl.appendChild(opt);

This will add just one more option, but I guess you get the point.

Here's a script that adds options, at targeted points, using the awesome power of jQuery (tested at jsBin):

// ==UserScript==
// @name     _Add new options at select points
// @include  http://play.pokemonshowdown.com/*
// @include  http://jsbin.com/azeveh*
// @require  http://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js
// ==/UserScript==

var selectNode  = $("#lobby-format");

selectNode  .find ("option[value='nu']")
            .after ('<option value="pu">PU (unrated)</option>');

selectNode  .find ("option[value='lc']")
            .after ('<option value="bwcup">BW Cup (unrated)</option>');

The OP's particular site uses AJAX to add that <select>. To compensate for AJAX, use the waitForKeyElements utility. Like so:

// ==UserScript==
// @name        _Add new options at select points, AJAX compensated.
// @include     http://jsbin.com/azeveh*
// @include     http://play.pokemonshowdown.com/*
// @require     http://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js
// @require     https://gist.github.com/raw/2625891/waitForKeyElements.js
// ==/UserScript==

waitForKeyElements ("#lobby-format option[value='nu']", AddOption_1);
waitForKeyElements ("#lobby-format option[value='lc']", AddOption_2);

function AddOption_1 (jNode) {
    jNode.after ('<option value="pu">PU (unrated)</option>');
}

function AddOption_2 (jNode) {
    jNode.after ('<option value="bwcup">BW Cup (unrated)</option>');
}