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

You could consider BLOCKQUOTE analogous to a DIV and Q analogous to SPAN.

Recommended usage is to enclose large quotes in BLOCKQUOTE and small, single line or sentence quotes in Q.

<blockquote>
    <p>This is a big quote.</p>
    <p>This is the second paragraph with a smaller <q>quote</q> inside</p>
</blockquote>

Cite is an attribute on either which merely points to the source.

According to this, "cite" is an attribute of q - and is not well supported at that.