As far as I can see, the example in the documentation is working, but not with the NASA JPL service. It says that NASA has stopped providing WMS support. You just have to look for another WMS service and fill in the required parameters:
urlWithParams = 'url=http://kaart.maaamet.ee/wms/alus&format=image/png&layers=MA-ALUS&styles=&crs=EPSG:3301'
rlayer = QgsRasterLayer(urlWithParams, 'MA-ALUS', 'wms')
QgsMapLayerRegistry.instance().addMapLayer(rlayer)
Be cautious, as if you don't fill out one of these parameters, because your WMS doesn't have one, QGIS will crash. In my example, the MA-ALUS layer doesn't have a style attribute, but I had to include it as an empty parameter.
Result:

UPDATE:
It works with QGIS 2.6.0, yaay!
from qgis.core import *
urlWithParams = 'url=http://kaart.maaamet.ee/wms/alus&format=image/png&layers=MA-ALUS&styles=&crs=EPSG:3301'
rlayer = QgsRasterLayer(urlWithParams, 'MA-ALUS', 'wms')
QgsMapLayerRegistry.instance().addMapLayer(rlayer)
UPDATE for QGIS 3:
It works with QGIS 3.2, after accounting for a https://qgis.org/api/api_break.html -- yaay!
from qgis.core import *
urlWithParams = 'url=http://kaart.maaamet.ee/wms/alus&format=image/png&layers=MA-ALUS&styles=&crs=EPSG:3301'
rlayer = QgsRasterLayer(urlWithParams, 'MA-ALUS', 'wms')
QgsProject.instance().addMapLayer(rlayer)
styles&is sufficient to get the default style for the layer. – nmtoken Mar 28 '18 at 17:32service=WMS&,request=GetMap&,version=1.3.0&,width=[num]&,height=[num]. Are these added on the fly by QGIS? – nmtoken Mar 28 '18 at 17:38http://kaart.maaamet.ee/wms/alus?format=image/png&, note too that the WMS specification tells us that the Ampersand follows the key/value pair so we should always expect an Ampersand at the end of a list of params. – nmtoken Mar 28 '18 at 17:41