What's the difference between functions and stored procedures? I heard that the difference between functions and stored procedures in SQL Server is that functions are not stored in the database while stored procedures are. 

Is that true?  If not, what are the differences between them?

In addition, I know that stored procedures are only complied once and then executed directly. What about functions?
A function attempts to return something, always, and has several restrictions - for example, you can not have any side effects, so you can't issue DML, call stored procedures, use dynamic SQL, call NEWID(), etc. You also cannot have error handling, transactions, or non-deterministic functions (e.g. GETDATE() in older versions, at least in SQL Server 2000 - though there are workarounds for this) defined inside a function.

There are several types of functions, mainly scalar and table-valued functions. Scalar functions can be called inline, e.g.

CREATE FUNCTION dbo.PrettyDate(@d DATETIME)
RETURNS CHAR(10)
AS
BEGIN
    RETURN(SELECT CONVERT(CHAR(10), @d, 120));
END
GO

DECLARE @Date DATETIME = CURRENT_TIMESTAMP;
SELECT dbo.PrettyDate(@Date);


Results:

----------
2012-03-14


Table-valued functions need to be called a little differently, since they act essentially like a parameterized view. For example:

CREATE FUNCTION dbo.DatesInRange
(
  @StartDate DATETIME,
  @EndDate   DATETIME
)
RETURNS TABLE  
AS  
  RETURN (SELECT [date] = DATEADD(DAY, n-1, @StartDate)
    FROM (SELECT n = ROW_NUMBER() OVER (ORDER BY [object_id])
      FROM sys.objects) AS x
      WHERE n &lt;= DATEDIFF(DAY, @StartDate, @EndDate) + 1
  );
GO

SELECT [date] 
  FROM dbo.DatesInRange('20120101', '20120105')
  ORDER BY [date];


Results:

date
-----------------------
2012-01-01 00:00:00.000
2012-01-02 00:00:00.000
2012-01-03 00:00:00.000
2012-01-04 00:00:00.000
2012-01-05 00:00:00.000


A stored procedure does not necessarily return data, but it can return more than one resultset. It can be used to affect data (update/insert/delete) and other side effects, can contain dynamic SQL, can have transactions, can have error handling, do not have restrictions about non-deterministic functions, and can call other stored procedures.

EDIT 

I am not quite sure what you mean by "function does not store in database." When you create either a stored procedure or a function, its definition is most certainly stored in the catalog view sys.sql_modules, and a reference to the module is created in sys.objects. There is a separate catalog view for stored procedures (sys.procedures) but there isn't an equivalent view for functions - you can still find those in sys.objects with types such as IF, FN and TF.

I will come back on the compile part of the question.