Should features be correlated or uncorrelated for classification?

Q1) Should highly correlated features with the target variable be included or removed from classification and regression problems? Is there a better/elegant explanation to this step?

Actually there's no strong reason either to keep or remove features which have a low correlation with the target response, other than reducing the number of features if necessary:

• It is correct that correlation is often used for feature selection. Feature selection is used for dimensionality reduction purposes, i.e. mostly to avoid overfitting due to having too many features / not enough instances (it's a bit more complex than this but that's the main idea). My point is that there's little to no reason to remove features if the number of features is not a problem, but if it is a problem then it makes sense to keep only the most informative features, and high correlation is an indicator of "informativeness" (information gain is another common measure to select features).
• In general feature selection methods based on measuring the contribution of individual features are used because they are very simple and don't require complex computations. However they are rarely optimal because they don't take into account the complementarity of groups of features together, something that most supervised algorithms can use very well. There are more advanced methods available which can take this into account: the most simple one is a brute-force method which consists in repeatedly measuring the performance (usually with cross-validation) with any possible subset of features... But that can take a lot of time for a large set of features.

However features which are highly correlated together (i.e. between features, not with the target response), should usually be removed because they are redundant and some algorithms don't deal very well with those. It's rarely done systematically though, because again this involves a lot of calculations.

Q2) How do we know that the dataset is linear when there are multiple variable involved? What does it mean by dataset being linear?

It's true that correlation measures are based on linearity assumptions, but that's rarely the main issue: as mentioned above it's used as an easy indicator of "amount of information" and it's known to be imperfect anyway, so the linearity assumption is not so crucial here.

A dataset would be linear if the response variable can be expressed as a linear equation of the features (i.e. in theory one would obtain near-perfect performance with a linear regression).

Q3) How to do feature importance for nonlinear case?

Information gain, KL divergence, and probably a few other measures. But using these to select features individually is also imperfect.