What exactly does homoiconicity mean?

Homoiconicy can mean different things to different people. Originally, it was defined in the context of the language TRAC, as such:

Because TRAC procedures and text have the same representation inside and outside the processor, the term homo-iconic is applicable, from homo meaning the same, and icon meaning representation.

However, that definition is problematic, because it is hard to precisely pin down what is meant by internal and external representations. It is also not at all what most people mean by it today.

Today, most people probably mean something along the lines of the accepted answer by Mike Yang here, namely that the represenation of structured data in the language is elegant (literal syntax), and that such datastructures are themselves the main means of representating code.

To confuse matters further, this concept is often called "code as data" (which is itself a very overloaded term).

More info here:

• Exploration of the original definition of homo-iconic
• Definition of homo-iconic as in current use

Scheme is homo-iconic because its programs have an interpretation as data structures.

'(define (foo x) (* x x))

is a list, the first element of which is define, the second (foo x) (a list), and so on. The quote mark ' means: don't interpret this, leave it as a list. If we remove the ' we get

(define (foo x) (* x x))

which is a Scheme function definition. Because Scheme program definitions are nested list expressions (and thereby a sort of "syntax tree literals"), and Scheme is a dynamic language, you can play tricks with this to build very powerful macro/code generating systems.

Now Java isn't homo-iconic simply because it doesn't provide these kind of "program literals" that evaluate to parse tree fragments. Of course, you can define a string

String helloWorld =
   "class Hello { public static void main(System.out.println(\"Hello, world!\"); }";

which you could parse and feed to a compiler, but that's awkward, because it's a string rather than a structured term.

It means "code as data" which is a general characteristic of Lisp family.

(add 2 3)

Just like above string, which is both a list and also a function call. The "Homo" prefix stands for this characteristic.