Drupal - How to theme a custom block

The way I do this is as follows...

function MYMODULE_block_info() {

  $blocks = [];

  $blocks['my_block_machine_name'] = [
    'info'  => t('My Block Title'),
    // @see https://api.drupal.org/api/drupal/includes!common.inc/group/block_caching/7.x
    // You can use different caching options.
    'cache' => DRUPAL_NO_CACHE,
  ];

  return $blocks;
}

function MYMODULE_block_view($delta = '') {

  $block = [];

  switch ($delta) {
    case 'my_block_machine_name':
      // Good idea to check user permissions here.
      if (user_access('access content')) {
        $block['subject'] = t('My Block Title');
        $block['content'] = MY_BLOCK_CONTENT_CALLBACK();
      }
      break;
  }

  return $block;
}

function MY_BLOCK_CONTENT_CALLBACK()() {

  $items = [];

  // This is the simplest kind of renderable array.
  $items['VAR_ONE'] = ['#markup' => 'VAR_ONE_OUTPUT'];

  // Here I added a prefix and a suffix.
  $items['VAR_TWO'] = [
    '#prefix' => '<div class="foo-bar">',
    '#markup' => 'VAR_TWO_OUTPUT',
    '#suffix' => '</div>',
  ];

  // This is where the $items get sent to your my-template.tpl.php template
  // that got registered below.
  return theme('my_cool_block', ['items' => $items]);
}

function MYMODULE_theme() {

  // Here you are registering your template for the block output above.
  $module_path = drupal_get_path('module', 'MYMODULE');

  // Drupal will now look up your modules /theme folder first to grab the
  // template.
  $base = [
    'path' => "$module_path/theme",
  ];

  return [
    'my_cool_block' => $base + [
        // Leave off .tpl.php.
        'template'  => 'my-template',
        // Define variables you want to pass to the template.
        // Here I just pass items, but you can pass any other data as well.
        'variables' => [
          'items' => NULL,
        ],
      ],
  ];
}

And then in a subfolder in your module called theme there should be a file called my-template.tpl.php which could have this in it:

<?php 

$items = $variables['items'];

print render($items['VAR_ONE']); 
print render($items['VAR_TWO']); 

And if you wanted to, you could actually overwrite the "default" module implementation you just made for my-module.tpl.php in your theme as you wish in block--MYMODULE--DELTA.tpl.php.

Try Theme Developer module. When you have enabled it you can check a checkbox in bottom left corner of you Drupal page. After that you can click on your block and get useful information considering theming. You can see the possible .tpl.php file namings for your block for example.

Pick one of those names. The first is the most specific one. It will only theme one block. Create a file with that name in your theme folder if it's not already there. You can put it in subfolder if you want to get organized.

Copy the content of block.tpl.php in your file and start changing things to the way you want them to be.

Save your file, clear caches and reload the page.

There's already a number of answers for this question but I have tried to provide a very simplistic approach. Hopefully identifying to devs the array structure expected by Drupal when returning your block content.

To do this I have broken the question down into separate code examples as such,

/**
 * Implements hook_theme().
 */
function examplemodule_theme() {
  return array(
    'examplemodule_output' => array(
      'variables' => array(
        'title' => NULL,
        'content' => NULL,
        'popular_content' => NULL,
       ),
      'template' => 'templates/examplemodule-sweet--block',
    ),
  );
}

Please see a full explanation here drupal 7 creating theming custom blocks