You cannot have arbitrary HTML in a wall post. If it looks like HTML, Facebook will strip it. The only other alteration Facebook will do I believe is convert text that looks like links into links (so if you have http://www.google.com somewhere in the message, Facebook will automatically turn it into a link).
However Facebook does provide basic facilities for including basic things like a picture, caption, description, link, etc through stream.publish by passing in additional parameters. This is an example for including a few of these things from Facebook's documentation (http://wiki.developers.facebook.com/index.php/Stream.publish):
$message = 'Check out this cute pic.';
$attachment = array(
'name' => 'i\'m bursting with joy',
'href' => 'http://icanhascheezburger.com/2009/04/22/funny-pictures-bursting-with-joy/',
'caption' => '{*actor*} rated the lolcat 5 stars',
'description' => 'a funny looking cat',
'properties' => array('category' => array(
'text' => 'humor',
'href' => 'http://www.icanhascheezburger.com/category/humor'),
'ratings' => '5 stars'),
'media' => array(array('type' => 'image',
'src' => 'http://icanhascheezburger.files.wordpress.com/2009/03/funny-pictures-your-cat-is-bursting-with-joy1.jpg',
'href' => 'http://icanhascheezburger.com/2009/04/22/funny-pictures-bursting-with-joy/')),
'latitude' => '41.4', //Let's add some custom metadata in the form of key/value pairs
'longitude' => '2.19');
$action_links = array(
array('text' => 'Recaption this',
'href' => 'http://mine.icanhascheezburger.com/default.aspx?tiid=1192742&recap=1#step2'));
$attachment = json_encode($attachment);
$action_links = json_encode($action_links);
$facebook->api_client->stream_publish($message, $attachment, $action_links);
Check this out for more info on what attachments you can include.