There is already an accepted answer, but I am adding this because I believe it can help others.
How many pixels are needed?
How "smooth" your image will look depends on its resolution which is measured in ppi (pixels per inch). The resolution depends on how many pixels your image contains and at which size you choose to print it.
resolution [px/inch] = width [px] / width [inch]
width [px] = width [inch] * resolution [px/inch]
width [inch] = width [px] / resolution [px/inch]
For standard quality print, a good rule of thumb for resolution is at least 300 ppi for images that are to be viewed at normal reading distance (like a card or a table image) and at least 180 ppi for larger images which are viewed from a distance (like posters for a room).
For example, a small poster at 15.7 x 15.7 inch should have the width and height:
15.7 inch * 180 px/inch = 2826 px
(Normally I wouldn't do this math manually. I would use "Image Size" in Photoshop or place the image in InDesign and use the "Info" panel to read the "effective ppi")
If your image is a lot lower than 300/180 ppi you could try scaling it up with bicubic interpolation, in Photoshop or some free image editor before printing. Then it won't have jagged pixels, but it will be blurry instead.
Which file format?
I don't know how the software you are using handles images, but ideally an image should be saved uncompressed (or compressed with non-destructive compression, lzw or zip) while editing. The pixels you place stays untouched. The downside is a larger file size which makes the image unsuited for the web.
Two of the most common "non-destructive" file formats for print are tif, which is recognized by most image applications, and psd, which is Photoshop's native format.
The most common compressed image format is jpg. A jpg image is compressed at a certain Quality between 0 and 12. Low quality is only used when file size is an issue. For print we want the highest possible quality, preferably 12.
It is common to only have access to compressed images. Many cameras, scanners and apps use the jpg format to save disk space. If your images is already compressed it won't change anything if you convert it to another format.
I believe most photo print shops would accept tif or jpg, where many general print shops would want a pdf because it is more unambiguous regarding document size and can have bleed applied, which is needed for most types of print.
There are many kinds of paper because there are many different requirements to paper. Uncoated paper has a nice rough touch and look, but cannot display as many colors as glossy photo paper. Glossy paper, on the other hand may give a result close to what you see on your screen, but it can look cheap and be hard to actually see when light reflects on its surface. In the end its all a matter of taste and need.
You should find the print shop you want to use and see if the have any samples you can look at. If the samples doesn't convince you, you could order prints of the same image on 2-3 different kinds of paper and then make your choice.
Impossible to answer. Depends on here you are in the world and the quality you expect.