Gmail recently added a rich text functionality to its signature editor. Until then, you could only have an insipid text, with no formatting. This was a huge enhancement.
Here is a screenshot of the current editor :

But if you want to style your signature a little bit, say you want to add a complex structure, such as a two column signature, you're unlucky !

The solution I came out with is more or less geeky one and will require you to know some HTML or have a less limited HTML editor.
For both cases you'll need to have Firebug installed. It's a Firefox addon you can get here :

Next :
1. Navigate to your "Settings" by clicking on the link at the top right corner of your GMail page : you end up in you General settings page.

Scroll down to the signature box.

2. Activate Firebug if it's not already on (you general hit F12 to fire it up).
Then click on the inspector pointer within Firebug to start exploring the content of the Gmail Settings page.
You're now inspecting the code, and Firebug automaticaly update whenever you hover a element of the page with the pointer.

3. Then click on the signature box to inspect it.

4. Go back to the Firebug's frame, make you you select the body element into the iframe wrapping the signature editor. Then right click on the corresponding html element and select "Edit HTML" in the menu.

5. Depending on you being an HTML expert excited about working around a Google limitation or a newbie afraid of all these coding stuffs, you can either edit the HTML content of you signature right into Firebug HTML Editor or copy and paste it from your favourite WYSIWYG Editor.
Make sure you style it properly and don't have your CSS tied to a external stylesheet.

That's it, for today, hope you'll come up with a GMail signature, much nicer than mine below :

Here is the HTML code I used :