Hi,
So far I mostly put labels and inputs inside a dedicated paragraph tag :
<p>
<label for="myInput">Blah</label>
<input type="text" ... />
</p>
But this tag is made for text paragraph. Is is semantically right to use it this way ? Should a div be used ?
Semantically, no, it is not correct. Your form inputs are not paragraphs in any sense of the word.
If you're a CSS expert, try using <ol> and <li> tags and restyling them to look how you like, since your form fields are an ordered list of items. See A List Apart's article on Prettier Accessible Forms for an example of the HTML and CSS necessary for this format.
You seem to have nearly answered your first question, in that it is semantically not a paragraph, so the use of <p> is -to me- wrong.
The second question of whether or not to use a <div> depends on your useage, but I don't see why not, other than the increasingly bulky code, though that'll probably not add much weight to the page.
My own tendency is to nest the <input /> within the <label> tag, though this is, again, semantically incorrect since the input is not a part of the label, being only its counterpart.
Of course, both ways work and produce much the same visual effect; I've never used an alternative -speech-converter or such- to a GUI browser, so I can't say if it adds weirdness for disabled users.