I'll list some practices I've found useful, hope this helps:

1. Irrespective of whether the data is huge or not, cross validation is a must when building any model. If this takes more time than an end consumer is willing to wait, you may need to reset their expectations, or get faster hardware/software to build the model; but do not skip cross validation. Plotting learning curves and cross-validation are effective steps to help guide us so we recognize and correct mistakes earlier in the process. I've experienced instances when a simple train-test set does not reveal any problems until I run cross-fold validations and find a large variance in the performance of the algorithm on different folds.

2. Before sizing up a dataset, eliminate the records with missing values of key variables and outliers, columns of highly correlated variables, and near zero variance variables - this will give you a much better estimate of the real usable dataset. Sometimes you may end up with only a fraction of the available dataset that can actually be used to build a model.

3. When sizing up a dataset for building a model, it is easier to estimate the computing resources if you enumerate the dataset in rows and columns and size of the final numeric matrix. Since every machine learning algorithm is ultimately going to convert the dataset into a numeric matrix, enumerating the dataset size in terms of GBs/TBs of raw input data (which may be mostly strings/textual nominal variables/etc.) is often misleading and may make a task more daunting and impossible than it it.

4. Once you know (or estimate) the final usable size of your dataset, check if you have a suitable machine to be able to load that into memory and train the model. If your dataset size is smaller than memory available/usable by the software, then you need not worry about the size any longer.

5. If the dataset size is larger than the memory available for the software to train a model, then you could use different approaches (starting from the simplest ones first) -

• Use a bigger machine: If you're using a cloud service provider then the simplest approach could be just to provision more memory and continue building the model as usual. For physical machines, try to procure additional RAM, its price continues to reduce and if your dataset is going to remain this big or grow bigger over time, then it is a good investment.
• Add nodes to the cluster: For Hadoop and Spark based deployments, training on larger data is as easy as adding new machines to the cluster.
• Most often classification tasks require training on data with highly imbalanced classes, ratio of positive and negative classes could sometimes be as large as 1:1000. A straightforward method to improve accuracy in these cases is to either over-sample the minority class or under-sample the majority class, or apply both methods together. If you have a large dataset, under-sampling the majority class is a very good option which will both improve your algorithm's accuracy as well as reduce training time.
• Build an ensemble: Split the dataset randomly and train several base learners on each part, then combine these to get the final prediction. This would most effectively make use of the large dataset and produce a more accurate model. But you need to spend more time to carefully build the ensemble and keep clear of the usual pifalls of ensemble building.
• When using an ensemble, train many single-thread models in parallel. Almost all ML software provide features to train multiple models or on different cores or separate nodes altogether.
• Evaluate multiple different algorithms on the time taken to train them for your specific dataset vs. their accuracy. While there is no universal answer, but I've found SVMs take much longer to train than regression models, but may be only slightly more accurate in performance; whereas a well built neural network model may take a very long time when compared to a CART tree, but perform significantly more accurately that the tree.
• To reduce time taken to build the model, try to automate as much of the process as you can. A few hours spent automating a complex error-prone manual task may save your team a hundred hours later in the project.
• If available, use those algorithm implementations which use parallel processing and cache aware computing, these reduce processing time significantly. For example, use xgboost instead of a single-core implementation of GBM.
• If nothing else works, train the model on a smaller dataset; as Emre has suggested in his answer, use learning curves to decide the smallest sample size is sufficient beyond which model accuracy does not improve noticeably. Refer to this article which describes that model performance quickly saturates when adding more training points beyond a certain stage - http://web.mit.edu/vondrick/largetrain.pdf.