Correct use of Blockquote, q and cite?

Yes. They are not presentational elements — blockquote represents a block quotation, q represents an inline quotation, and cite represents a reference to a name, work, standard, URL, etc.

You do have some validation errors that are fairly common with blockquote. A blockquote element cannot be inside a paragraph, and in HTML4 actually needs to contain paragraphs. The nesting of the p and blockquote elements in your fragment needs to be reversed.

The blockquote element (also the q element) can optionally have a cite attribute to specify a URI where the quote came from. HTML5 says user agents should make that link available to the user, and HTML4 doesn't say anything at all. I would include the URI both in the cite attribute and as an inline link, since browsers don't handle it.

Here's how I would write that fragment, with those revisions in mind:

<blockquote cite="http://stackoverflow.com">
  <p>Type HTML in the textarea above, <q>and it will magically
  appear</q> in the frame below.</p>
</blockquote>
<p>
  <cite><a href="http://stackoverflow.com">reference url</a></cite>
</p>

Validate this fragment

The other answers on this page are out of date, but the question is still valid.

The q element semantically represents a quotation, and is an inline element. It should be used like so (ie. no block elements inside it):

<p>
   In the words of <cite>Charles Bukowski</cite> -  
   <q>An intellectual says a simple thing in a hard way. 
   An artist says a hard thing in a simple way.</q>
</p>

Another example:

<p>
    <q>This is correct, said Hillary.</q> is a quote from the 
    popular daytime TV drama <cite>When Ian became Hillary</cite>.
</p> 

The q element should not be placed inside a blockquote element, as it would be redundant -- both denote a quote.

A blockquote is a block element, allowing other block elements to be placed inside:

  <blockquote>
    <p>My favorite book is <cite>At Swim-Two-Birds</cite>.</p>
    - <cite>Mike Smith</cite>
  </blockquote>

<cite> is an inline element representing the title of a body of work. Since the W3C and WHATWG have now agreed to work together, we have one answer as to what it may contain: The name of a book, a film, a TV show, a game, a song, a play, etc, etc.

It should NOT be a URL or an author's name (a URL can be added with a normal a element and an author is not a piece of work that you're citing).

This is a valid usage:

<figure>
 <blockquote>
  <p>The truth may be puzzling. It may take some work to grapple with.
  It may be counterintuitive. It may contradict deeply held
  prejudices. It may not be consonant with what we desperately want to
  be true. But our preferences do not determine what's true.</p>
 </blockquote>
 <figcaption>Carl Sagan, in "<cite>Wonder and Skepticism</cite>", from
 the <cite>Skeptical Inquirer</cite> Volume 19, Issue 1 (January-February
 1995)</figcaption>
</figure>