A fast way to delete all rows of a datatable at once

As someone mentioned, just use:

dt.Rows.Clear()

This will allow you to clear all the rows and maintain the format of the DataTable.

dt.Rows.Clear();

There is also

dt.Clear();

However, calling Clear() on the DataTable (dt) will remove the Columns and formatting from the DataTable.

Per code found in an MSDN question, an internal method is called by both the DataRowsCollection, and DataTable with a different boolean parameter:

internal void Clear(bool clearAll)
{
    if (clearAll) // true is sent from the Data Table call
    {
        for (int i = 0; i < this.recordCapacity; i++)
        {
            this.rows[i] = null;
        }
        int count = this.table.columnCollection.Count;
        for (int j = 0; j < count; j++)
        {
            DataColumn column = this.table.columnCollection[j];
            for (int k = 0; k < this.recordCapacity; k++)
            {
                column.FreeRecord(k);
            }
        }
        this.lastFreeRecord = 0;
        this.freeRecordList.Clear();
    }
    else // False is sent from the DataRow Collection
    {
        this.freeRecordList.Capacity = this.freeRecordList.Count + this.table.Rows.Count;
        for (int m = 0; m < this.recordCapacity; m++)
        {
            if ((this.rows[m] != null) && (this.rows[m].rowID != -1))
            {
                int record = m;
                this.FreeRecord(ref record);
            }
        }
    }
}

If you are running your code against a sqlserver database then
use this command

string sqlTrunc = "TRUNCATE TABLE " + yourTableName
SqlCommand cmd = new SqlCommand(sqlTrunc, conn);
cmd.ExecuteNonQuery();

this will be the fastest method and will delete everything from your table and reset the identity counter to zero.

The TRUNCATE keyword is supported also by other RDBMS.

5 years later:
Looking back at this answer I need to add something. The answer above is good only if you are absolutely sure about the source of the value in the yourTableName variable. This means that you shouldn't get this value from your user because he can type anything and this leads to Sql Injection problems well described in this famous comic strip. Always present your user a choice between hard coded names (tables or other symbolic values) using a non editable UI.