How do I convert a PNG to SVG, using software?

So you are looking for raster to vector graphics converter/tracer. potrace & autotrace both are in Ubuntu repository. Myself I tried potrace before which gave nice results with default options. As I remember, both tools do not support compressed formats as input, only bitmap images.

See Potrace examples

Potrace: utility to transform bitmaps into vector graphics

potrace is a utility for tracing a bitmap, which means, transforming a bitmap into a smooth, scalable image. The input is a bitmap (PBM, PGM, PPM, or BMP format), and the default output is an encapsulated PostScript file (EPS). A typical use is to create EPS files from scanned data, such as company or university logos, handwritten notes, etc. The resulting image is not "jaggy" like a bitmap, but smooth. It can then be rendered at any resolution.

Command:

potrace -s inputfile

AutoTrace: bitmap to vector graphics converter

AutoTrace is a program for converting bitmaps to vector graphics. The aim of the AutoTrace project is the development of a freely-available application similar to CorelTrace or Adobe Streamline. In some aspects it is already better. Originally created as a plugin for the GIMP, AutoTrace is now a standalone program.

Command:

autotrace -output-format svg inputfile

References:

• man potrace
• man autotrace

Update

• There are more GUI that added tracing feature, like Gimp & Inkscape. See Hussein El Motayam's answer.

• Here also Wikipedia: Comparison of raster-to-vector conversion software, not every tool. To anyone interested in comparing results, I would like to ask reporting results to free open source tools so they can ameliorate.

Inkscape has got an awesome auto-tracing tool.

1. Install Inkscape using sudo apt-get install inkscape
2. Import your image
3. Select your image
4. From the menu bar, select Path > Trace Bitmap Item
5. Adjust the tracing parameters as needed

Check their tracing tutorial for more information.

Once you are comfortable with the tracing options. You can automate it by using CLI of Inkscape.

Use the convert command in the terminal :

For example:

convert EXAMPLE.png EXAMPLE.svg

Here's some info from the manpage:

convert(1) - Linux man page

Name

convert - convert between image formats as well as resize an image, blur, 
          crop, despeckle, dither, draw on, flip, join, re-sample, and much more.

Synopsis

convert [input-options] input-file [output-options] output-file