The 99% invisible podcast discusses exactly this: http://99percentinvisible.org/episode/octothorpe/

As quoted from the accompanying article:

Whether called hash, pound, number sign, lumberyard — the symbol traces back to Ancient Rome.

Its story starts with the Latin term Libra Pondo, meaning “pound in weight.” This was abbreviated to lb, which we still use. When lb became standard, it was often drawn with a little bar across the tops of both letters (℔), just to show that the l and the b were connected. As scribes started writing this sign faster and faster, lb began to morph.

Over time, the symbol’s meaning started to bifurcate — it was used for the unit pound, and it also started to be used as a number sign. It was important enough to wind up on typewriter keyboards, which helped it survive.

Fast forward to 1963. the invention of the touch tone telephone.

The touch tone phone used buttons instead of a rotary wheel, and so unlike previous phones, the numbers no longer had to be arranged in a circle on the dial.

Bell Laboratories, a research subsidiary of AT&T, experimented with a few different designs for the telephone key pad. They tried arranging the numbers in two rows of five, in a circle, in a cross, in a step pattern, but ended up arranging the numbers 1 to 9 in a 3×3 grid, and put zero alone at the bottom center. 

In 1968, Bell Labs  they decided to add keys on either side of the zero. This would make the keypad into a nice even rectangle, and give users a few more options on a phone menu.

Unlike rotary phones, touch tone phones allow you to continue to dial after the connection has been made, enabling the new telephone systems, such as automated menus. Additional buttons, they realized, could be handy in this regard. They settled on the asterisk (*) and the number, or pound sign (#), mostly because they were symbols that they knew computers would be able to recognize and were already on the standard QWERTY keyboard.