What happens when we add an index to an existing table with a large amount of data? I've a table which will contain around ~15 Million records. Now I need to add an index to the table.

Adding an index will take some time to update every entry in the table.

I'm quite confused whether adding the index will cause downtime.

If yes, then how can I overcome the downtime?
With plain CREATE INDEX, the table will be locked for writes but not reads. 

Use CREATE INDEX CONCURRENTLY to avoid write locks as well.

From the PostgreSQL docs on CREATE INDEX:


  When this option is used, PostgreSQL will build the index without
  taking any locks that prevent concurrent inserts, updates, or deletes
  on the table; whereas a standard index build locks out writes (but not
  reads) on the table until it's done. There are several caveats to be
  aware of when using this option — see Building Indexes Concurrently.


And more specifically (Like @ypercube commented):


  PostgreSQL supports building indexes without locking out writes. This
  method is invoked by specifying the CONCURRENTLY option of CREATE INDEX.
   When this option is used, PostgreSQL must perform two scans of
  the table, and in addition it must wait for all existing transactions
  that could potentially use the index to terminate. Thus this method
  requires more total work than a standard index build and takes
  significantly longer to complete. However, since it allows normal
  operations to continue while the index is built, this method is useful
  for adding new indexes in a production environment.


Bold emphasis mine.