When to create Indexes? I have a stored procedure that takes around 2 minutes to execute. The execution plan suggested me to create a non clustered index on a table (which is a high traffic table with millions of records in it, plus it gets a constant stream of data every single second).

Please help me decide on whether I should create an index on that table or not.

Note: I tried creating a non clustered index on that table (on development server) and the time was reduced to 40 seconds from 2 minutes.
You haven't really given enough information about the original execution plan, what it changed to or what columns you put in the new NCI.  It is possible that the query performance can be improved even further.  The cost of the new index is the initial build, the additional processing of entries on INSERT and UPDATE and potentially the fragmentation maintenance.  Also, it's possible it may require some statistics maintenance if the data profile is likely to change.

It is possible that the index could improve overall system performance by reducing read access to the clustered index, but with a table changing so rapidly, the cost of maintaining the index might be very high.  On the other hand, you have to look at the overall requirements.  If this query only runs once a month, perhaps it is too high to bear.  If it runs 10 times a hours, then running it in a few seconds, with inserts slightly slower might be a small price to pay.

A thing to look out for would be index fragmentation if there are a lot of updates because the NCI key is not static.