8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes.
Earlier Edit: It appears that the answer is "yes," either by an already existent publication or by combining the Guo reference mentioned below with the answer here (and a remark on cycles admitting graceful labelings). But I have not been able to track down an accessible reference, and hope that someone can find one!
Note: Perry Iverson points out that the graphs described below go by different names, and suggests an answer already exists in the literature. I am adding a reference-request tag in the hopes that someone can find a proof of the full characterization. According to Gallian's A Dynamic Survey of Graph Labeling (pdf), there is some work due to Wenfu Guo, who (from the citation below) is using notation similar to mine - even if they are called dragons rather than balloons.
However, it is clear that the proof alluded to below is not bidirectional (or is mis-stated) since it discusses only the cases when the cycle is congruent to $1$ or $2$ (mod $4$), yet Leen Droogendijk's approach can be extended to gracefully label $B(n,k)$ whenever $n \equiv 0$ or $3$ (mod $4$); precisely the complementary cases! Moreover, the image from Wikipedia clearly shows a graceful labeling in which the cycle is congruent to $3$ (mod $4$).
I will gladly accept an answer with an accessible version of the work by Guo (or by anyone else who has managed a characterization of such graphs).
The wikipage on graceful labelings includes the following diagram:
Quoting from the page:
In graph theory, a graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers between $0$ and $m$ inclusive, such that no two vertices share a label, and such that each edge is uniquely identified by the positive, or absolute difference between its endpoints.
Let us call a graph a balloon if it consists of an $n$-cycle with a single strand (string) emanating from one of the vertices in the aforementioned cycle. Furthermore, let us require the balloon component to have $n \geq 3$ vertices and the string component to have an additional $k \geq 1$ vertices; in such a case, we denote the balloon as $B(n,k)$.
For example, the diagram above depicts $B(3,2)$, i.e., a balloon with a $3$-cycle (the vertices labeled $0, 4, 5$ make up the balloon component) and a length $2$ string (emanating from the vertex $0$).
Fact: For all $k \geq 1$, the balloon $B(3,k)$ admits a graceful labeling.
(Proof: Left to reader.)
Question: Which balloons admit graceful labelings?
For example, can anyone prove that $B(4,k)$ admits a graceful labeling for all $k \geq 1$?
Alternatively, can anyone come up with an $n \geq 3$ and $k \geq 1$ for which $B(n,k)$ does not admit a graceful labeling?
A word of caution: The conjecture that all trees admit graceful labelings is a notoriously difficult open problem. (For a related MSE post, see here.) Ideally, I would wish for a full characterization of the gracefulness of balloons; however, I will certainly up-vote responses with non-trivial contributions (and may simply "accept" one, particularly if the question here can be transformed into one that implies the conjecture for trees).