Great uneasiness exists all along the Indian frontier. Nearly all the regular troops have been withdrawn from the West for service in the South. With the return of the warm weather it seems certain that the red skins will take advantage of the opportunity thus offered, and inaugurate a bitter and vindictive fight against the whites. Rumors come from the agencies that the Indians are leaving in numbers. A feverish excitement among them has been easily to be detected. Their ponies are now in good condition, and forage can soon be had in abundance on the prairie, if it is not already. Everything points toward a sudden and startling outbreak of hostilities. [SPECIAL DESPATCH TO THE NEW YORK HERALD.] ST. PAUL, June 22, 1861. The Sioux near here are all in a ferment. Experienced Indian fighters say the signs of a speedy going on the war-path are not to be mistaken. No one can tell how soon the whole frontier may be in a bloody blaze. The women and children are rapidly coming in from all exposed settlements. Nothing overt as yet has transpired, but that the Indians will collide very soon with the settlers is certain. All the troops have been withdrawn. In our defenceless state there is no knowing how many lives may be lost before the regiments of volunteers now organizing can take the field. LATER. THE WAR BEGUN. FIRST BLOOD FOR THE INDIANS. THE SCALPING KNIFE AND THE TOMAHAWK AT WORK AGAIN. [SPECIAL DESPATCH TO THE NEW YORK HERALD.] BLACK WING AGENCY, June 22, 1861. The Indians made a sudden and unexpected attack on the town of Coyote Hill, forty miles from here, last night, and did much damage before the surprised settlers rallied and drove them off. The red skins met with heavy losses. Among the whites killed are a man named William Beaver, sometimes called Beaver Bill, and his wife. Their child, a beautiful little girl of two, was carried off by the red rascals. A party has been made up to pursue them. Owing to their taking their wounded with them, the trail is very distinct. DOCUMENT NO. 15. _Letter from Mrs. Edgar Saville, in San Francisco, to Mr. Edgar Saville, in Chicago:_ CAL. JARDINE'S Monster Variety and Dramatic Combination. ON THE ROAD. _G.W.K. McCULLUM, Treasurer HI. SAMUELS, Stage Manager. FNO. SHANKS, Advance_. _No dates filled except with first-class houses. Hall owners will please consider silence a polite negative._ SAN FRANCISCO, January 29, 1863.