That terminal is called the Linux console, or sometimes a “vt” (short for virtual terminal). The terminology can be confusing, especially since it's used inconsistently and sometimes incorrectly. You can find more information on terminology by reading What is the exact difference between a 'terminal', a 'shell', a 'tty' and a 'console'?.
The Linux console supports user-configured fonts, so the answer to your question is “whatever the user set up”. The utility to change the font is consolechars, part of the Linux console tools. Only 8-bit fonts are supported by the hardware, though you can partly work around this by supporting unicode-encoded output but only having 256 glyphs (other characters are ignored). Read the lct documentation (online as of this writing, it should be included in your distribution's package) for more information.
If you use the Linux framebuffer, you can have proper unicode support, either directly or through fbterm.
The half-block characters are included in IBM code page 437, which is supported in ROM most PC video adapters. Depending on what characters you need, this may be enough.
Note that very few people use the Linux console these days. Some people cannot use it for various reasons (not running Linux, running on a remote X terminal, having a video adapter where text mode is buggy, …). I don't recommend spending much energy on supporting it.
The solution was much simpler. I had to go to the GUI settings for gnome-terminal, visit Terminal -> Set Character Encoding -> UTF-8.
-- To keep this as the default in Ubuntu (and sorry to find out that it's a distro-specific solution in this SE forum):
gconftool --set --type=string /apps/gnome-terminal/profiles/Default/encoding en_US.UTF-8
Best Answer
if you are using MATE with the default terminal emulator start the MATE Terminal and open the menu Edit - Profile Preferences - tab General, uncheck Use the system fixed width font and choose your desired font.