What does "semantically correct" mean?

Semantics basically means "The study of meaning".

Usually when people are talking about code being semantically correct, they're referring to the code that accurately describes something.

In (x)HTML, there are certain tags that give meaning to the content they contain. For example:

An H1 tag describes the data it contains as a level-1 heading. An H2 tag describes the data it contains as a level-2 heading. The implied meaning behind this is that each H2 under an H1 is in some way related (i.e. heading and subheading).

When you code in a semantic way, you basically give meaning to the data you're describing.

Consider the following 2 samples of semantic VS non-semantic:

<h1>Heading</h1>
<h2>Subheading</h2>

VS a non-semantic equivalent:

<p><strong>Heading</strong></p>
<p><em>Subheading</em></p>

Sometimes you might hear people in a debate saying "You're just talking semantics now" and this usually refers to the act of saying the same meaning as the other person but using different words.

Labeling correctly

It means that you're calling something what it actually is. The classic example is that if something is a table, it should contain rows and columns of data. To use that for layout is semantically incorrect - you're saying "this is a table" when it's not.

Another example: a list (<ul> or <ol>) should generally be used to group similar items (<li>). You could use a div for the group and a <span> for each item, and style each span to be on a separate line with a bullet point, and it might look the way you want. But "this is a list" conveys more information.

Fits the ideal behind HTML

HTML stands for "HyperText Markup Language"; its purpose is to mark up, or label, your content. The more accurately you mark it up, the better. New elements are being introduced in HTML5 to more accurately label common web page parts, such as headers and footers.

Makes it more useful

All of this semantic labeling helps machines parse your content, which helps users. For instance:

• Knowing what your elements are lets browsers use sensible defaults for how they should look and behave. This means you have less customization work to do and are more likely to get consistent results in different browsers.
• Browsers can correctly apply your CSS (Cascading Style Sheets), describing how each type of content should look. You can offer alternative styles, or users can use their own; as long as you've labeled your elements semantically, rules like "I want headlines to be huge" will be usable.
• Screen readers for the blind can help them fill out a form more easily if the logical sections are broken into fieldsets with one legend for each one. A blind user can hear the legend text and decide, "oh, I can skip this section," just as a sighted user might do by reading it.
• Mobile phones can switch to a numeric keyboard when they see a form input of type="tel" (for telephone numbers).