You know, this actually isn't a half-bad question, and I'll add as much information as possible.
You want your texture resolution to be as detailed as it needs to be. Large terrain textures like grass and dirt should be 512x512 or 1024x1024. Smaller assets like the texture for a grenade or bullet, something that isn't very big or something that the user doesn't see often, can be smaller, say 128x128 or even 64x64. It all depends on what level of detail you're shooting for. I would say the absolute maximum for a texture should be 1024x1024, because if you go bigger than that, you might run into memory issues. A texture can be as small as 16x16 and still look good, as well, so it's really up to you, and there is no "right answer".
Unity imports all popular image file formats. Here are some of the most popular ones, and their benefits/drawbacks.
PNG: My personal favorite. Large filesizes, but maximum quality. PNG32 allocates 32 bytes per pixel, and saves images with the best quality. I recommend this file format over all others, but it's personal preference, really.
PNG supports transparency, but you need to ensure that the "Matte" in some programs is set to "Transparent", otherwise your transparent image will be saved with a white background, and your transparency will be lost.
JPG/JPEG: I do not recommend the JPG file format, as it automatically includes compression that can ruin the quality of your texture. If you are using JPG, be sure to set the "Quality" level to 100, or "Maximum", this way, no compression is done on the image, and you retain the highest quality. Anything lower than 100% quality, you will start to see artifacting and a huge loss of quality.
JPG does not support transparency, so if you have a transparent texture, do not save it as a JPG file. JPGs can handle large, high quality images, but only if the quality settings are set to absolute "Maximum" when saving/exporting.
GIF: I also do not recommend the GIF file format, simply because it's hard to retain maximum quality, as well. There are many different settings and alpha transparency options, and there are a lot of ways your image could be exported with poor quality settings. GIF is also 23 years old, and in my opinion, isn't up to the task of handling high-quality gaming textures.
GIF handles transparency, but not very well. Again, I don't recommend this file format.
BMP: BMP files are typically uncompressed, so their filesizes are very large. However, because they're uncompressed, they retain all of their quality. So if you don't mind dealing with huge filesizes, you could use the BMP format for textures.
The BMP file format does not work with transparent textures.
PSD: Unity will import .PSD files straight from Photoshop (it will flatten all visible layers and create a texture automatically). So, if you're working with Photoshop, this might be your best option, because .PSDs retain full image quality. Plus, when you save the image in Photoshop after you make changes, Unity's Asset Importer will automatically detect the change, and update the texture in your game, without you having to do anything. This is actually true for all textures/filetypes, but the PSD needs special notice because Unity automatically flattens all visible layers for you, so you can edit the source in Photoshop without making "export copies" or something like that, it's just easier to organize.
So my personal preference is PNG, simply because there aren't a lot of settings to mess around with, and you automatically get the highest image quality possible. That, or PSD, but I know not everyone has the luxury of being able to use Photoshop. :)
And yes, to answer your specific question, you can absolutely use Paint Shop Pro to make textures, since textures are just image files. Like I said before, if Paint Shop Pro exports/saves to PNG format, you're good to go! :)