How can I create a custom block

allowing menus to be placed in any region. It is also possible to add arbitrary html content as a new block through "add block".

By looking at the blocks page it appears modules can insert their own blocks. The question is how is this done.